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.

Sources: Wikipedia: Bitwise operation, MDN: Bitwise AND (&)

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; }

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

def find_unique(nums):
    acc = 0
    for n in nums:
        acc ^= n
    return acc

def set_bit(mask, i): return mask | (1 << i)
def clear_bit(mask, i): return mask & ~(1 << i)
def has_bit(mask, i): return (mask & (1 << i)) != 0

function findUnique(array $nums): int {
    $acc = 0;
    foreach ($nums as $n) $acc ^= $n;
    return $acc;
}
function setBit(int $mask, int $i): int { return $mask | (1 << $i); }
function clearBit(int $mask, int $i): int { return $mask & ~(1 << $i); }
function hasBit(int $mask, int $i): bool { return ($mask & (1 << $i)) !== 0; }

    public static int findUnique(int[] nums) {
        int acc = 0;
        for (int n : nums) acc ^= n;
        return acc;
    }

    public static int setBit(int mask, int i) { return mask | (1 << i); }

    public static int clearBit(int mask, int i) { return mask & ~(1 << i); }

    public static boolean hasBit(int mask, int i) { return (mask & (1 << i)) != 0; }

    public static int FindUnique(int[] nums) {
        int acc = 0;
        foreach (int n in nums) acc ^= n;
        return acc;
    }

    public static int SetBit(int mask, int i) { return mask | (1 << i); }

    public static int ClearBit(int mask, int i) { return mask & ~(1 << i); }

    public static bool HasBit(int mask, int 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?

Use Bit manipulation when the problem statement says “find the single or unique number using XOR”, “set, clear, toggle, or test a bit” or “pack many yes/no flags into one integer”. A solution built on it usually runs in O(1)/O(n).

• •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

The signal words of every pattern sit in one table, the algorithm patterns cheat sheet.

What is Bit manipulation confused with?

Bit manipulation is most often confused with Hash set / map, Math and number theory (GCD, sieve, modular), Backtracking and Non-comparison sort (counting / radix).

• 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?

Interview problems solved with Bit manipulation include Single number, Number of 1 bits, Counting bits, Missing number, Subsets, Power of two and Sum of two integers.

• 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?

The target complexity of Bit manipulation is O(1)/O(n).

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