What is bit manipulation?
Bit manipulation works directly on the binary representation of a number using AND, OR, XOR,
NOT, and the shift operators << and >>. No loop over digits, no string conversion —
just operators that flip, compare, and slide bits in a single CPU instruction.
- Bit
- A single binary digit, 0 or 1 — one position in a number's binary form
- XOR
^— 1 where two bits differ, 0 where they match; XOR-ing a bit twice returns it to where it started- Shift
<<and>>slide every bit left or right — the same as multiplying or dividing by 2
Why bit manipulation at all?
Picture a bank of light switches, one per bit. Flipping a switch is XOR: hit it once and it turns on, hit the very same switch a second time and it turns off again — no matter what state it started in.
That's the whole trick behind problems like finding the one number that doesn't have a pair: XOR every value together, and every pair of switches gets flipped twice and cancels itself out, leaving only the one that was only ever flipped once.
Flip the same switch twice and it's back to off — that's why pairs cancel under XOR.
What kinds of problems does it solve?
A handful of small moves cover most bit manipulation problems. Learn to recognize the shape, and the operator to reach for follows almost automatically.
AND, OR, and XOR side by side
AND keeps a bit only where both inputs have it set. OR keeps a bit where either input
has it set. XOR keeps a bit only where the inputs disagree — the one that's useful for
spotting differences and cancelling duplicates.
Same two numbers, three different results — the operator decides what survives.
Clear the lowest set bit
n & (n - 1) turns off the lowest 1 bit and leaves every bit above it untouched. Repeat it and
count the rounds, and you've counted the set bits — no loop over every bit position required.
Every round removes exactly one 1 bit, until nothing is left.
Isolate the lowest set bit
n & (-n) keeps only the lowest 1 bit and zeroes out everything else. In two's complement,
-n is ~n + 1, which flips every bit up through that lowest 1 — AND-ing the two leaves
just that one bit standing.
Every other bit falls away — only the lowest 1 survives.
Shift to multiply or divide
n << 1 slides every bit one place left, which is exactly the same as multiplying by 2. n >> 1
slides right, dividing by 2 and dropping the remainder. Shifting by k multiplies or divides by
2^k in one instruction.
Every bit slides one place left — the value doubles.
Two moves worth memorizing
Underneath the specific problems, almost everything comes back to two habits: a small set of bit tricks you reach for by pattern, and masks that pick out or wipe a specific range of bits.
The power moves
n & (n - 1) clears the lowest set bit. n & (-n) isolates it. x ^ x is always 0,
which is exactly why XOR-ing a value into a running result twice cancels it — the mechanism behind
finding the one number in an array that doesn't have a pair.
Every pair cancels under XOR — only the unpaired value survives.
function singleNumber(nums: number[]): number {
let result = 0;
for (const num of nums) {
result ^= num; // pairs cancel, the lone value survives
}
return result;
}
function clearLowestSetBit(n: number): number {
return n & (n - 1);
}
function isolateLowestSetBit(n: number): number {
return n & -n;
}
Masks select or clear a range
(1 << k) - 1 builds a mask of k ones — every bit below position k is set, every
bit above it is 0. AND with that mask to keep only the low k bits; AND with its NOT to
clear them instead.
(1 << 4) - 1 keeps the low 4 bits and wipes the rest.
function lowKBits(n: number, k: number): number {
const mask = (1 << k) - 1; // k ones: 0b0...0111...1
return n & mask; // keep only the low k bits
}
function clearLowKBits(n: number, k: number): number {
const mask = (1 << k) - 1;
return n & ~mask; // wipe the low k bits, keep the rest
}
Where it works — and where it breaks
The XOR-cancels-pairs trick leans on a quiet assumption: every value you don't care about shows up an even number of times. Break that assumption and the same trick gives you a number that means nothing.
Works when duplicates pair up
Every value except one appears exactly twice. XOR-ing everything together cancels every pair down to 0, and 0 XOR-ed with the lone value just returns that value — the trick is provably correct.
Breaks when a value appears three times
If a "duplicate" value actually appears an odd number of times, it doesn't fully cancel — it leaks its own bits into the result. The plain XOR trick now returns a number that isn't the answer to anything.