Bit Tricks
XOR cancels pairs, and-minus-one strips the lowest set bit, and shifts enumerate subsets.
Bit ManipulationO(1) or O(log n)New18 problems
18
mastery
Trigger phrases
If a problem statement sounds like one of these, try this pattern first.
single number
count set bits
power of two
subsets via masks
The template
Get this into muscle memory, then adapt the condition per problem.
let x = 0;
for (const n of nums) x ^= n; // duplicates cancel
const lowest = x & -x; // isolate lowest set bit
const count = () => { let c = 0; while (x) { x &= x - 1; c++; } return c; };If you are stuck
The generic hint ladder for this pattern, in order.
- 1Every element appears twice except one. What operation cancels pairs?
- 2XOR is associative and commutative, so order does not matter.
- 3To split two unique numbers, partition by any bit where they differ.
Drill it
Every problem in the bank that uses this pattern.
0 / 18 solved