Bit Manipulation Basics

A Java int is 32 bits and a long is 64 bits. Bit 0 is the lowest (worth 1), bit 1 is worth 2, bit k is worth 2^k. So 13 is 1101: 8 + 4 + 1.

Negative numbers use two's complement: -x is stored as all the bits of x inverted, plus one. In 8 bits, 5 is 0000 0101; inverted it is 1111 1010; adding one gives 1111 1011, which is -5. The top bit (bit 31 for an int) is 1 for every negative number. Some consequences come up in problems:

• -1 is all ones: 1111…1111.
• The range is uneven: -2,147,483,648 to 2,147,483,647. Math.abs(Integer.MIN_VALUE) is still negative.
• Addition and subtraction work the same way for negative and positive numbers, which is why the hardware uses this format.

Java has no unsigned int, so problems about "unsigned" values work with the bit pattern of an ordinary int. Integer.toUnsignedString and Integer.toBinaryString help when printing.

Two Java pitfalls cause real bugs:

• Shift distances wrap. For an int, Java takes the shift distance modulo 32, so 1 << 32 is the same as 1 << 0, which is 1, not 0. For a long it is modulo 64. Use 1L << k when k can reach 32 or more.
• Precedence. &, ^ and | bind more loosely than ==, so x & 1 == 0 does not compile. Write (x & 1) == 0.

Most of the clever solutions on this site rely on four properties of XOR:

• x ^ x = 0: equal values cancel.
• x ^ 0 = x: zero is neutral.
• Order does not matter: XOR is commutative and associative.
• It is its own inverse: if a ^ b = c, then a ^ c = b.

So XORing a list in which values appear in pairs leaves only the unpaired ones, whatever the order. That is the idea behind Single Number, Missing Number and Find the Difference. The inverse property is what makes prefix XOR work.

The JDK also has these built in, and the JIT compiler turns many of them into single CPU instructions: Integer.bitCount, Integer.numberOfTrailingZeros, Integer.numberOfLeadingZeros, Integer.highestOneBit, Integer.lowestOneBit, Integer.reverse and Integer.rotateLeft, with the same methods on Long.

public class BitTricks {

    public static void main(String[] args) {
        int x = 0b1011_0100;                                  // 180

        System.out.println((x >> 2) & 1);                     // 1   is bit 2 set?
        System.out.println(x | (1 << 0));                     // 181 set bit 0
        System.out.println(x & ~(1 << 2));                    // 176 clear bit 2
        System.out.println(x ^ (1 << 7));                     // 52  toggle bit 7
        System.out.println(x & -x);                           // 4   lowest set bit
        System.out.println(x & (x - 1));                      // 176 clear the lowest set bit
        System.out.println(Integer.bitCount(x));              // 4   number of 1 bits
        System.out.println(Integer.numberOfTrailingZeros(x)); // 2   index of the lowest set bit

        System.out.println(-8 >> 1);                          // -4          sign bit copied in
        System.out.println(-8 >>> 1);                         // 2147483644  zero copied in
        System.out.println(1 << 32);                          // 1   shift distance is taken mod 32
        System.out.println(1L << 32);                         // 4294967296

        byte b = (byte) 0xF0;
        System.out.println(b);                                // -16  bytes are signed
        System.out.println(b & 0xFF);                         // 240  read it as unsigned
    }
}

An int can store a set of up to 32 items, one bit each; a long holds 64. Set operations become single instructions:

• union: a | b; intersection: a & b; difference: a & ~b;
• "no item in common": (a & b) == 0;
• size: Integer.bitCount(a).

Maximum Product of Word Lengths stores each word's letters as a 26-bit mask. Looping mask from 0 to (1 << n) - 1 visits every subset of n items, which is the basis of bitmask dynamic programming. Java's EnumSet and BitSet use the same idea internally.