Bitwise operations

a & b has a 1 in each position where both a and b have a 1. ANDing with a mask keeps the bits that are 1 in the mask and clears the rest, which is how you extract bits.

Use the widget to try every operator. Pick an operator, enter a and b, and the result is built one bit column at a time. The display shows 8 bits, but Java computes on 32 bits; the low 8 bits are identical. The same widget covers OR, XOR, NOT and the shifts below.

1int and  = a & b;     // 1 only where both bits are 1
2int or   = a | b;     // 1 where at least one bit is 1
3int xor  = a ^ b;     // 1 where the bits differ
4int not  = ~a;        // flip every bit
5int shl  = a << b;    // shift left, fill with 0
6int shr  = a >> b;    // arithmetic shift right: copy the sign bit
7int ushr = a >>> b;   // logical shift right: fill with 0

a | b has a 1 wherever at least one of a and b has a 1. ORing with a mask sets those bits without touching the others. It is the standard way to combine flags: READ | WRITE.

Example: 12 | 10 = 1100 | 1010 = 1110 = 14. Select the OR operator in the widget above and check the table.

1final int READ = 1, WRITE = 2, EXEC = 4;
2int permissions = READ | WRITE;                  // 3
3boolean canWrite = (permissions & WRITE) != 0;   // true
4permissions |= EXEC;                              // add a flag: 7
5permissions &= ~WRITE;                            // remove a flag: 5

a ^ b has a 1 wherever the bits differ. XOR with a mask flips the bits where the mask has a 1. Its key properties are a ^ a = 0, a ^ 0 = a, and that it is commutative and associative. Together these mean XOR undoes itself: (a ^ b) ^ b = a.

Example: 12 ^ 10 = 1100 ^ 1010 = 0110 = 6. XOR is the key to the tricks in lesson 6.05.

~a flips every bit, so ~a == -a - 1. For example ~5 = -6 and ~0 = -1. Because it flips all 32 bits of an int, the result is almost always negative for small non-negative numbers.

Use it to build a mask that clears bits: x & ~mask keeps every bit of x except those set in the mask.

1int x = 5;                    // 0000 0101
2int y = ~x;                   // 1111 1010 = -6
3int clearLow3 = x & ~7;       // clears the low three bits (7 = 0b111)

a << k moves every bit k places toward the high end and fills the vacated low bits with 0. Mathematically it multiplies by 2^k, as long as the result does not overflow. Select a << b in the widget and step through the shifts: bits that move past the top are lost.

The shift distance is taken modulo the width: for an int it is k & 31, for a long k & 63. So 1 << 32 is 1, not 0. Use 1L << k for k up to 63.

1int a = 3 << 2;               // 12 (3 * 4)
2int big = 1 << 31;            // -2147483648 (sets the sign bit)
3int wrap = 1 << 32;           // 1, because 32 & 31 == 0
4long ok = 1L << 40;

a >> k moves bits toward the low end and fills the vacated high bits with a copy of the sign bit. For negative numbers the new bits are 1s, so the result is still negative. It divides by 2^k, rounding toward negative infinity: -5 >> 1 is -3, not -2.

Try -16 >> 2 in the widget: the top two positions fill with 1s and the result is -4.

1System.out.println( 16 >> 2);   //  4
2System.out.println(-16 >> 2);   // -4
3System.out.println( -5 >> 1);   // -3  (floor of -2.5)
4System.out.println( -5 / 2);    // -2  (division truncates toward zero)

a >>> k also moves bits toward the low end, but always fills the high bits with 0. It treats the value as unsigned. For non-negative numbers it equals >>. For negative ints it produces a large positive number: -1 >>> 28 is 15 (the top four bits of an all-ones int are cleared).

The widget's >>> works on the 8-bit view of the value, so -16 >>> 2 gives 60 there; in Java on a 32-bit int it gives 1073741820. Use >>> when you treat the bits as a bit pattern rather than a number, for example when extracting fields or reading hash bits.

1System.out.println(-1 >>> 28);                     // 15
2System.out.println(-16 >>> 2);                     // 1073741820
3int hashBits = (h >>> 16) & 0xFFFF;                // extract the upper half of a hash
4int mid = (lo + hi) >>> 1;                         // safe midpoint even if lo + hi overflows into the sign bit

Bitwise operators have lower precedence than comparison operators, which catches many people out. In order from highest to lowest: + -, then shifts << >> >>>, then < <= > >=, then == !=, then &, then ^, then |, then &&, then ||.

So x & 1 == 0 is parsed as x & (1 == 0), which does not compile for an int. Always write (x & 1) == 0. When in doubt, add parentheses.