Bit Manipulation

Every integer is stored as binary — a row of 0s and 1s. Bit manipulation operates on those bits directly with & (AND), | (OR), ^ (XOR), ~ (NOT), and the shifts << and >>. The payoff: many problems that look like they need a loop collapse into one or two operations.

The core operators

1. 1a & b (AND) keeps a 1 only where both inputs have a 1.
2. 2a | b (OR) keeps a 1 where either input has a 1.
3. 3a ^ b (XOR) keeps a 1 where the inputs differ. Key facts: a ^ a = 0 and a ^ 0 = a.
4. 4x << k shifts left by k bits (multiply by 2ᵏ); x >> k shifts right (divide by 2ᵏ).

Check, set, and clear one bit

1 << i is a mask with a single 1 at position i. Combine it with the operators to touch exactly that bit:

// Is bit i set?  ->  1 if set, 0 if not
const isSet = (n >> i) & 1;

// Set bit i to 1
const withBit = n | (1 << i);

// Clear bit i to 0
const cleared = n & ~(1 << i);

// Toggle bit i
const flipped = n ^ (1 << i);

Counting set bits with n & (n−1)

Subtracting 1 flips a number's lowest 1 to 0 and turns the zeros below it into 1s; AND-ing with the original then clears exactly that lowest 1 and leaves everything else alone. So n & (n−1) removes one 1 per step — repeat until zero to count the 1s (the popcount).

1. 1Start with 13 = 1101 (three 1s).
2. 213 & 12 = 1101 & 1100 = 1100 = 12 — one 1 removed (count 1).
3. 312 & 11 = 1100 & 1011 = 1000 = 8 — another removed (count 2).
4. 48 & 7 = 1000 & 0111 = 0000 = 0 — last removed (count 3). Done: 3 set bits.