Pattern Guide
Bit Manipulation
"XOR is your best friend. Masks are your toolkit."
Bit manipulation solves problems that look hard in O(1) or O(n) using only integer arithmetic. Learn XOR properties, bit masking, counting tricks, and bitmask DP for subset enumeration.
15 min readbit problems →
Problems you can solve with this pattern
9 problems · click any to start solving
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 matterBit 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 |
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)