Common bit tricks

To read bit i, shift it down to position 0 and mask with 1: (n >> i) & 1. Or build a mask with a single 1 at i and check for non-zero: (n & (1 << i)) != 0. Either works, and the second does not need the result to be exactly 1.

The widget lets you pick any of the tricks in this lesson, with n and i, and shows the intermediate rows. Choose “Test bit i” first.

1static boolean test(int n, int i) { return ((n >> i) & 1) == 1; }
2static boolean test2(int n, int i) { return (n & (1 << i)) != 0; }

1boolean test(int n, int i)    { return ((n >> i) & 1) == 1; }
2int set(int n, int i)         { return n | (1 << i); }
3int clear(int n, int i)       { return n & ~(1 << i); }
4int toggle(int n, int i)      { return n ^ (1 << i); }
5int lowestSetBit(int n)       { return n & -n; }
6int removeLowestSetBit(int n) { return n & (n - 1); }
7boolean isPowerOfTwo(int n)   { return n > 0 && (n & (n - 1)) == 0; }

To force bit i to 1, OR with a mask that has only bit i set: n | (1 << i). If the bit was already 1 nothing changes. In the widget, choose “Set bit i”.

To set several bits at once, OR with the combined mask: n | 0b1010.

1static int set(int n, int i) { return n | (1 << i); }

To force bit i to 0, AND with a mask that has every bit set except bit i: n & ~(1 << i). The ~ turns the single-bit mask into the inverse mask.

To clear the lowest k bits use n & ~((1 << k) - 1), or (n >> k) << k.

1static int clear(int n, int i) { return n & ~(1 << i); }

To flip bit i, XOR with the single-bit mask: n ^ (1 << i). A 0 becomes 1 and a 1 becomes 0, and every other bit is unchanged. Applying it twice restores the original.

Toggling is how you flip light switches in a bitmask puzzle: each move is one XOR.

1static int toggle(int n, int i) { return n ^ (1 << i); }

n & -n keeps only the lowest set bit of n. Because -n is ~n + 1, below the lowest set bit both n and -n are 0, at that bit both are 1, and above it they are complements, so the AND keeps just that one bit. For 44 (0010 1100) the result is 4.

This is the building block of Fenwick trees (Chapter 29), where i & -i is the step size, and it is used to iterate over set bits.

1static int lowestSetBit(int n) { return n & -n; }   // 44 -> 4, 40 -> 8, 0 -> 0
2int index = Integer.numberOfTrailingZeros(n);       // its position

n & (n - 1) clears the lowest set bit. Subtracting 1 turns the lowest 1 into 0 and every 0 below it into 1, so ANDing with n removes exactly that bit. For 44 (0010 1100) it gives 40 (0010 1000).

Repeating it until n is 0 visits each set bit once, which is Brian Kernighan's way to count bits.

1static int removeLowestSetBit(int n) { return n & (n - 1); }   // 44 -> 40 -> 32 -> 0

A positive number is a power of two if it has exactly one set bit, which means removing the lowest set bit leaves 0: n > 0 && (n & (n - 1)) == 0. The n > 0 check is needed because 0 & -1 is also 0, and negative numbers are not powers of two.

Run “Is 64 a power of two?” and “Is 44 a power of two?” in the widget to see n - 1 and the AND result.

1static boolean isPowerOfTwo(int n) { return n > 0 && (n & (n - 1)) == 0; }
2// 64 -> true, 44 -> false, 1 -> true, 0 -> false, Integer.MIN_VALUE -> false

Brian Kernighan's algorithm counts set bits by clearing the lowest set bit until none are left: while (n != 0) { n &= n - 1; count++; }. It takes one iteration per set bit, not one per bit position. Step through 108 and then 255 to compare.

A simple loop that tests all 32 positions always takes 32 steps. In practice use Integer.bitCount, which the JIT compiles to a single CPU instruction (popcnt) on most hardware.

1static int popCount(int n) {
2    int count = 0;
3    while (n != 0) {
4        n &= n - 1;              // clears the lowest set bit
5        count++;
6    }
7    return count;
8}