What bit manipulation is
Every whole number is secretly a row of on/off switches — its bits. The number
13 is 1101: the switches for 8, 4 and 1 are on, the switch for 2 is off (8 + 4 + 1 = 13).| value | 8 | 4 | 2 | 1 |
|---|---|---|---|---|
| 13 | 1 | 1 | 0 | 1 |
| 6 | 0 | 1 | 1 | 0 |
Four operators flip and combine whole rows of switches at once:
- AND (
&) — a switch stays on only if both rows have it on - OR (
|) — on if either row has it on - XOR (
^) — on only where the rows disagree (a flip) - shift (
<<,>>) — slide the whole row left or right
The simplest question you can ask a number is "is your lowest switch on?" — that's
n & 1, and it answers "is n odd?" (equivalently, not divisible by 2), with no division at all. That one tiny trick is the seed for everything that follows.Learn a trick, then spend it
Bit manipulation is a bag of small tricks. The way to learn it is one trick at a time — learn what an operator does, then immediately spend it on a real question.
Trick 1 —
n & 1 reads the lowest switch. Spend it: even vs odd (divisible by 2) with no % and no division — just look at the last bit.Trick 2 —
a ^ a = 0 and a ^ 0 = a. XOR-ing a value with itself cancels to zero. Spend it: the classic "find the single number" — in a list where every value appears twice except one, XOR the whole list and the pairs annihilate, leaving the loner.Trace "find the single number" on [4, 1, 2, 1, 2]
| step | XOR in | running acc |
|---|---|---|
| start | — | 0 |
| ^ 4 | 4 | 4 |
| ^ 1 | 1 | 5 |
| ^ 2 | 2 | 7 |
| ^ 1 | 1 | 6 (the first 1 cancels) |
| ^ 2 | 2 | 4 (the first 2 cancels) |
4 is the survivor — O(n) time, O(1) space, no hash map. In the animation, watch the running accumulator in binary: when a value arrives for the second time, exactly the bits it set the first time flip back off — the pair annihilates. Before each step, predict the accumulator; by the last step only the loner's bits survive.This section has a step-by-step animation in the interactive lesson.
console.log(6 & 1); // 0 — 6 is even: lowest switch off
console.log(7 & 1); // 1 — 7 is odd: lowest switch on
function findUnique(nums) {
let acc = 0;
for (const n of nums) {
acc ^= n;
}
return acc;
}
console.log(findUnique([4, 1, 2, 1, 2])); // 4Quick check
Predict: XOR of the whole list [7, 3, 7] is…
Answer it in the interactive lesson to keep your progress.
Where it breaks (and how not to get burned)
- Operator precedence.
&,|,^bind looser than==and+, sox & 1 == 0parses asx & (1 == 0). Parenthesize:(x & 1) == 0. - Signed 32-bit surprises. JS bitwise ops coerce to signed 32-bit; large numbers and the sign bit can bite. Watch
>>>(unsigned) vs>>(sign-preserving). - Confusing
&/|with&&/||. The single-character ones are bitwise, not logical — a very common slip.
Quick check
For a right shift in bit-counting loops, prefer >>> because…
Answer it in the interactive lesson to keep your progress.
You learned it — now apply it twice
Same flow, one more trick.
n & (n - 1) clears the lowest set bit — subtracting 1 flips the lowest 1 (and the zeros beneath it), so ANDing with the original wipes exactly that one switch.Spend that single trick two ways:
- Is
na power of two? A power of two has exactly one switch on, son & (n - 1)clears it straight to0. Checkn > 0 && (n & (n - 1)) === 0. - Count the set bits. Keep clearing the lowest
1and counting until nothing is left — you loop once per set bit, not once per bit.
Count the 1s in
13 (binary 1101):console.log(16 & (16 - 1)); // 0 — one switch on, so n & (n-1) clears it (16 is a power of two)
function countSetBits(n) {
let count = 0;
while (n) {
n = n & (n - 1); // clear the lowest set bit
count++;
}
return count;
}
console.log(countSetBits(13)); // 3 — 1101 has three 1sQuick check
n = 12 (binary 1100). Predict n & (n - 1).
Answer it in the interactive lesson to keep your progress.
How fast is it? (complexity)
Using the vocabulary from the Complexity & Time lesson, every bitwise operation is
O(1) — it acts on a fixed 32-bit row of switches in one step, whatever the number's size. So the single-number sweep is O(n) time and O(1) space, beating the hash map's O(n) memory.A pocket cheat-sheet of the
O(1) idioms you've now met:n & 1— is the lowest bit on? (odd / not divisible by 2)n & (1 << k)— is bitkon? ·n | (1 << k)— turn bitkonn & (n - 1)— clear the lowest set bit (loop it to count bits)a ^ a = 0— XOR cancels equal pairs
Key takeaways:
- Numbers are rows of bits; AND / OR / XOR / shift act on them in
O(1). - Learn one trick, then spend it:
& 1→ even/odd,^→ find the loner,& (n - 1)→ count bits. - Parenthesize bitwise ops (
&binds looser than===); mind signed 32-bit and>>>vs>>.
The same switch-flipping mindset powers a family of classics, each its own lesson later (no need to know them yet): power of two & counting bits (the
& (n - 1) trick — animated in See it), Gray code (list numbers so each differs from the next by exactly one bit), and subset masks (treat an integer's bits as a set, then enumerate all 2ⁿ subsets just by counting 0 … 2ⁿ − 1). Next up in order: Dynamic Programming — reusing overlapping sub-answers instead of recomputing them.console.log(5 & 1); // 1 — 5 is odd, lowest switch on
console.log(5 | (1 << 1)); // 7 — turn on bit 1: 101 | 010 = 111
console.log(5 ^ 5); // 0 — a value XOR itself cancels to 0