Bit twiddling

Manipulating integer values in terms of their actual binary representation in the computer.

Integer types

Integer operators

Arithmetic operators you learned in CSA: +, -, *, /, and %.

Bitwise operators: &, |, ~, and ^.

Shift operators: <<, >>, and >>>

Bitwise operators

Operators that combine two int values bit by bit.

Three of them are analogous to the boolean operators &&, ||, and ! if you think of each bit as representing a boolean value with 1 being true and 0 being false.

&, |, and ~.

Also ^ performs an “exclusive or” or “xor”.

Bitwise and

Bitwise or

Bitwise not

Bitwise xor

&

01101000010011000110100000011000 01011111110101001010001000011000

⇓

01001000010001000010000000011000

|

01101000010011000110100000011000 01011111110101001010001000011000

⇓

01111111110111001110101000011000

~

01101000010011000110100000011000

⇓

10010111101100111001011111100111

^

01101000010011000110100000011000 01011111110101001010001000011000

⇓

00110111100110001100101000000000

Shifting operators

Operators that produce new values by shifting the bits to the left (moving each bit to a more significant position) or right (moving each bit to a less significant position).

Three flavors of shift

• << left shift

• >> arithmetic right shift (fills with sign bit)

• >>> logical right shift (fills with zeros)

Arithmetic shifts

<< and >> are equivalent to multiplying or dividing by a power of 2 since each individual bit moves to a higher or lower power of two.

1000 >> 2 ⟹ 250

1000 << 4 ⟹ 16000

Shifting examples

x << 8

11101000010011000110100000011000 01001100011010000001100000000000

x >> 8

11101000010011000110100000011000 11111111111010000100110001101000

x >>> 8

11101000010011000110100000011000 00000000111010000100110001101000

Some subtleties

Casting

Casting an integer value to a larger type, e.g. byte to int promotes the value by filling the extra bits with the sign bit (i.e. the most significant bit).

E.g., the byte -86 (10101010 in bits) cast to an int becomes 11111111111111111111111110101010.

Casting to a smaller type just chops off the extra bits. So 11111111111111111111111110101010 would go back to 10101010.

Promotion

All the integer operators produce either int or long results.

All operands are promoted as if by being cast to int unless any of the operands are long in which case everything is promoted to long.

This is similar to double contaigon but it happens even if none of the operands are ints or longs.

Recipes

Make a mask with a single bit a position p

(Where the least significant bit is at position 0.)

1 << p

Integer.toBinaryString(1 << 4) ⟹ "10000"

Make n consecutive 1 bits:

(1 << n) - 1

Integer.toBinaryString((1 << 4) - 1) ⟹ "1111"

Make n consecutive 1 bits with the rightmost 1 at position p

((1 << n) - 1) << p

Integer.toBinaryString(((1 << 4) - 1) << 3) ⟹ "1111000"

Bit patterns

Masking

If you only care about certain bits you can mask out all the others. For instance, to keep only the top three bits of a byte (positions 5-7 inclusive) from b:

b & 0b11100000

or

b & 0xe0

or

b & ((1 << 3) - 1) << 5

A note on masking

Remember the & operator promotes its operands to ints.

Thus if b is a byte, b & 0xff will give you an int consisting of the eight bits from b and the rest zeros, i.e. a positive value, even if b was negative.

This is useful if you want an unsigned 8-bit quantity from 0 to 255, rather than from -128 to 127.

Masking and shifting

After masking sometimes it’s convenient to shift the bits you kept into a specific position to check if they are equal to some value:

((b & 0xe0) >>> 5) == 6

Checks if b matches the bit pattern 110xxxxx.

Shifting and masking

Alternatively, you can shift the bits you care about into the bottom of an int and then mask:

((b >>> 5) & 0x7) == 6

Also checks if b matches the bit pattern 110xxxxx.

Or a third way

(b & 0xe0) == 0xc0

Keeps the top-three bits of a byte and zeros everything else out. If those three bits were 110 then the value as an int will be 0xc0.