Bit Manipulation

Bit manipulation treats integers as arrays of bits. A handful of operators plus a few classic tricks handle everything from fast arithmetic to subset enumeration, and they underlie Fenwick trees, Bloom filters, and much of low-level systems code.

The Operators

^ is the workhorse: x ^ x = 0 and x ^ 0 = x, so XOR cancels duplicates — the classic “find the single non-duplicated number in an array” problem is a single pass of XOR.

The Core Idioms

x & (x - 1)      // clear the lowest set bit
x & -x           // isolate the lowest set bit (lowbit)
x | (x + 1)      // set the lowest clear bit
x ^ (x & -x)     // toggle the lowest set bit

// set / clear / toggle / test the k-th bit
x |  (1 << k)      // set
x & ~(1 << k)      // clear
x ^  (1 << k)      // toggle
(x >> k) & 1       // test

lowbit(x) = x & −x is the heart of the Fenwick tree: it returns the value of the lowest set bit, so index arithmetic walks responsibility ranges in O(log n).

Counting and Checking

• Popcount — x & (x−1) repeatedly counts set bits in O(popcount); or use hardware __builtin_popcount.
• Parity — XOR all bits together.
• Power of two — x != 0 && (x & (x − 1)) == 0.
• Trailing zeros — __builtin_ctz, or iterate x >>= 1 while x & 1 == 0.

Subset Enumeration

A bitmask over n elements is an n-bit integer, and iterating over its submasks is a classic competitive-programming pattern:

sub = mask
while sub:
    process sub
    sub = (sub - 1) & mask

This visits every subset of mask in O(3^n) total across all masks — the backbone of DP over subsets (e.g. the Travelling Salesman in O(2^n · n)).

Where You’ll Use It

• Fenwick trees — lowbit-driven range sums.
• Flags and permissions — packing several booleans into one integer.
• Hashing and Bloom filters — bitwise OR of hash bits.
• Compression and encoding — packing fields into a word.
• DP over subsets — mask-represented states.

Practice Trajectory

1. Verify every idiom above by hand on 8-bit values.
2. Implement popcount and power-of-two checks without loops.
3. Solve: single non-duplicate number (XOR), missing number, reverse bits.
4. Implement subset enumeration and a 2^n subset-sum DP.
5. Use lowbit to rebuild the Fenwick build/query loops.

When It’s the Right Tool