Bit Manipulation

A number in memory is a row of switches. 44 is not stored as the digits 4 and 4 — it is stored as eight on-or-off bits, each standing for a power of two:

 0    0    1    0    1    1    0    0
128   64   32   16   8    4    2    1
           32 + 8 + 4 = 44

Flip the switches and watch the value change. The three readouts underneath update live — they are explained just below:

Everything in this article follows from that picture.

The five operators

Shifting left by one doubles; shifting right by one halves and throws away the remainder. x << 3 is x * 8.

The four things you will actually write

const check  = (x: number, n: number) => (x >> n & 1) === 1;   // is bit n on?
const set    = (x: number, n: number) => x | (1 << n);         // turn it on
const clear  = (x: number, n: number) => x & ~(1 << n);        // turn it off
const toggle = (x: number, n: number) => x ^ (1 << n);         // flip it

Each one builds 1 << n — a mask with a single bit — and combines it. clear inverts the mask first, so it is all 1s except at position n, and ANDing with that keeps everything except that bit.

XOR is the interesting one

Three properties, each surprising the first time:

x ^ x === 0        // anything cancels itself
x ^ 0 === x        // zero changes nothing
a ^ b === b ^ a    // order does not matter

Put them together. Take an array where every value appears twice except one:

const odd = values.reduce((acc, v) => acc ^ v, 0);

Every pair cancels to 0, order is irrelevant, and the loner is left standing. One pass, no memory, no hash map.

Two tricks worth memorising

x & (x - 1) clears the lowest set bit.

Subtracting 1 flips the lowest 1 to 0 and turns every 0 below it into 1. ANDing keeps only the bits above, which erases exactly that one bit:

x       = 0b0010_1100
x - 1   = 0b0010_1011
x & …   = 0b0010_1000     ← the lowest 1 is gone

So counting set bits takes as many iterations as there are bits set, not 32:

let count = 0;
while (x !== 0) { x &= x - 1; count += 1; }

And x & (x - 1) === 0 tests for a power of two: exactly one bit set means clearing it leaves nothing.

x & -x isolates the lowest set bit.

Negation in two’s complement is “flip every bit, then add 1”, which leaves the lowest 1 in place and inverts everything above it. AND them and only that bit survives. This is what Fenwick trees use to walk their index structure.

Bitmasks as sets

If your universe has at most 32 items, a whole subset fits in one integer.

let inParty = 0;
inParty |= 1 << WIZARD;                   // add
inParty &= ~(1 << THIEF);                 // remove
const hasWizard = (inParty >> WIZARD & 1) === 1;

const both  = partyA & partyB;            // intersection
const either = partyA | partyB;           // union
const onlyA = partyA & ~partyB;           // difference

Set operations become single instructions, and for (let mask = 0; mask < 1 << n; mask++) enumerates every subset. This is what makes bitmask dynamic programming practical for $n \le 20$ or so.

When it is worth it

Rarely, for speed. Compilers already turn x * 8 into a shift, and modern CPUs have a single instruction for population count. Writing x << 3 to “optimise” a multiply is noise.

It is worth it when bits are genuinely the model:

• Flags and permissions — one integer holding sixteen booleans, which is why Unix file modes look like 0644.
• Subset enumeration in DP and search.
• Bloom filters and other probabilistic structures.
• Fenwick trees, whose entire index arithmetic is i & -i.
• Hardware and protocol work, where the layout is fixed by a spec.

The rest of the time, prefer the readable version. A comment explaining a bit trick is a sign the trick was not worth it.