Pattern Reference
Bit Manipulation
"XOR tricks, bit hacks, Brian Kernighan, subset enumeration via bits, gray code, bitmask DP."
Loading...
Deep Dive Tutorial
Bit manipulation is about exploiting binary representation directly. The key insight is that XOR, AND, OR, and shifts can express complex operations extremely efficiently. Once you internalize a handful of bit tricks, a large class of problems that look hard suddenly become O(n) or even O(1).
Essential Bit Tricks
Core operations reference
// Check if bit k is set
(n >> k) & 1 // 1 if set, 0 if not
// Set bit k
n | (1 << k)
// Clear bit k
n & ~(1 << k)
// Toggle bit k
n ^ (1 << k)
// Lowest set bit (isolate rightmost 1)
n & (-n) // = n & (~n + 1)
// Clear lowest set bit
n & (n - 1) // also: check if n is power of 2 → n & (n-1) === 0
// Count set bits (Brian Kernighan)
let count = 0;
while (n) { n &= (n - 1); count++; } // each step removes lowest set bit
// XOR properties:
// a ^ a = 0 (cancel)
// a ^ 0 = a (identity)
// XOR is commutative and associative → order doesn't matter| See This | Think This |
|---|---|
| "find the single number" among duplicates | XOR all — duplicates cancel, single remains |
| "find missing number in [1..n]" | XOR all with 1..n — everything cancels except missing |
| "subsets / enumerate all subsets" | Bitmask: 0..2^n-1, each bit = include/exclude element |
| "is power of 2" | n > 0 && (n & (n-1)) === 0 |
| "count 1 bits" | Brian Kernighan: n &= (n-1) until 0, count steps |
| "number of different bits" | Count set bits in a XOR b |
Worked Problems
More Worked Problems
brain
Bit trick cheat sheet:
- Clear lowest set bit:
- Isolate lowest set bit:
- Check power of 2:
- Count set bits: Brian Kernighan's loop —
- XOR cancelation:
- Swap without temp:
- Bitmask DP: enumerate subsets of mask with
- Clear lowest set bit:
x & (x-1)- Isolate lowest set bit:
x & (-x)- Check power of 2:
x > 0 && (x & (x-1)) === 0- Count set bits: Brian Kernighan's loop —
while(x) { count++; x &= x-1; }- XOR cancelation:
a ^ a = 0 and a ^ 0 = a- Swap without temp:
a ^= b; b ^= a; a ^= b;- Bitmask DP: enumerate subsets of mask with
for(sub=mask; sub>0; sub=(sub-1)&mask)