Bit manipulation

How does Bit manipulation work?

A number is a row of bits, each worth twice the one to its right. Bit i is worth 2 to the power i.

Shifting left by one doubles the number. Shifting right by one halves it and drops the last bit.

AND with a mask keeps only the bits the mask holds. That is how you read a single bit.

OR sets a bit and XOR flips it. A bit XORed with itself always becomes zero.

That last fact is the whole trick behind finding a lone value. Every pair cancels out.

n AND n minus one clears the lowest set bit. Repeating that counts the set bits.

1. n = 1100Twelve written in binary. Two of its bits are set.
2. n & 1 = 0The last bit is zero, so the number is even.
3. n >> 2 = 11Shifting right twice leaves three.
4. n & (n - 1) = 1000Subtracting one gives 1011, and the AND clears the lowest set bit.
5. two rounds reach zeroSo twelve has exactly two bits set.

function findUnique(nums) {
    return nums.reduce((acc, n) => acc ^ n, 0);
}
function setBit(mask, i) { return mask | (1 << i); }
function clearBit(mask, i) { return mask & ~(1 << i); }
function hasBit(mask, i) { return (mask & (1 << i)) !== 0; }

A worked example of Bit manipulation

Count the set bits of every number

For every number from 0 to n, count how many of its bits are set.

Counting each one separately works, but it repeats a lot of work.

Clearing the lowest set bit gives a smaller number, already counted.

So bits[i] is one more than bits[i AND i minus one].

function countBits(n) {
    const bits = new Array(n + 1).fill(0);

    for (let i = 1; i <= n; i++) {
        // i & (i - 1) clears the lowest set bit, so it is always smaller
        bits[i] = bits[i & (i - 1)] + 1;
    }

    return bits;
}

When should you use Bit manipulation?

These phrases in a problem statement point here:

• •find the single or unique number using XOR
• •set, clear, toggle, or test a bit
• •pack many yes/no flags into one integer
• •count set bits or check a power of two

What is Bit manipulation confused with?

• Hash set / map: A set answers membership for any key at all. A bitmask does it for 32 known items, with no memory.
• Math and number theory (GCD, sieve, modular): Both work on the number itself. That page is about divisors and primes, this one about bits.
• Backtracking: Subsets can be listed by counting from zero upward. Backtracking builds the same list recursively.
• Non-comparison sort (counting / radix): Radix sort reads digits, sometimes as bits. Its goal is grouping, never flipping.

Common mistakes with Bit manipulation

• Shifting past 31 bits

  JavaScript bit operators work on 32 bits and wrap around. Use BigInt beyond that.

• Forgetting the sign bit

  The result of a shift can come back negative. Use the unsigned shift for a plain count.

• Mixing up AND and OR

  AND reads or clears, while OR sets. Getting them backwards gives a silently wrong mask.

• Reaching for bits when clarity matters

  A boolean array reads better and runs just as fast. Use a mask when memory is the constraint.

Which interview problems use Bit manipulation?

• Single number: Every pair cancels itself out under XOR.
• Number of 1 bits: Clear the lowest set bit until nothing is left.
• Counting bits: Each answer reuses a smaller one already computed.
• Missing number: XOR the indices against the values.
• Subsets: Count from zero to two to the power n.
• Power of two: True exactly when n AND n minus one is zero.
• Sum of two integers: XOR gives the sum, AND shifted gives the carry.

What is the time and space complexity of Bit manipulation?

O(1)/O(n)

One operation is O(1) on a 32-bit value. Looping the bits is O(32), which counts as constant.