Lesson 34.2 · Bit Manipulation

Everyday Bit Tricks

Test, set, clear and toggle bit i; isolate or remove the lowest set bit; count bits. Each is one expression.

12 min

Think of it like this

A checklist printed as a row of boxes: you can look at box i, tick it, untick it, or find the first ticked box, each with one quick glance.

1.The toolkit

Test bit i: (n >> i) & 1. Set: n | (1 << i). Clear: n & ~(1 << i). Toggle: n ^ (1 << i).

Lowest set bit: n & -n (the basis of Fenwick trees). Remove the lowest set bit: n & (n − 1). Repeating that until n is 0 counts set bits in O(number of ones) (Brian Kernighan). Integer.bitCount(n) does it in hardware.

Power of two: n > 0 and (n & (n − 1)) == 0, because a power of two has exactly one set bit.

Main.java

public class Main {
    public static void main(String[] args) {
        int n = 44;                                          // 101100
        System.out.println("n = " + Integer.toBinaryString(n));
        System.out.println("lowest set bit (n & -n) = " + (n & -n));
        System.out.println("drop lowest (n & (n - 1)) = " + (n & (n - 1)));
        System.out.println("bitCount = " + Integer.bitCount(n));
        System.out.println("bit 3 is " + ((n >> 3) & 1));
        System.out.println("set bit 0 -> " + (n | 1));
        System.out.println("clear bit 2 -> " + (n & ~(1 << 2)));
    }
}

Output

n = 101100
lowest set bit (n & -n) = 4
drop lowest (n & (n - 1)) = 40
bitCount = 3
bit 3 is 1
set bit 0 -> 45
clear bit 2 -> 40

Remember

(n >> i) & 1 to test.
n & (n − 1) drops the lowest one.
n & −n isolates it.

Common mistakes

Using 1 << 31 or larger shifts with int when you need long (1L << i).

Command Palette

Everyday Bit Tricks

1.The toolkit