Bit manipulation

The bit manipulation coding pattern for interviews. Masks, shifts, number & (number - 1) and XOR tricks, with a step-through, templates in Java, Python, C#, Go and TypeScript, and 10 LeetCode problems.

Mid-level13 min read

Every integer is stored as a row of bits, each 0 or 1. Bit i, counting from 0 on the right, is worth 2 to the power i. So 44 is 101100: 32 + 8 + 4. Bit manipulation means working on those bits directly, with operators that change all of them at once in a single CPU step.

Interview problems use bits for two reasons. Some questions are about bits, such as counting them or reversing them. Others have a neat answer when you think in bits. “Find the number without a pair” needs a hash set, or one XOR loop with O(1) memory. A handful of identities cover almost every problem. Learn those, and say what each one does to the bits.

How to spot it

The question names bits: “number of 1 bits”, “reverse bits”, “power of two”, “Hamming distance”.
“Every element appears twice except one” or “one number is missing”. XOR cancels the pairs.
“Without using + or -” or “without extra memory”. The answer must come from the bits.
A small set of choices, like up to 20 items or 26 letters. A set can then be one integer, where bit i says whether item i is in. That’s a bitmask.
Flags or permissions packed into one number.

If the numbers are just values, such as prices or counts, bits rarely help. Reach for a hash map first, and keep bits for when the question pushes you there.

Watch it run

Count the 1 bits of 44 with number & (number - 1). Watch what number - 1 does to the lowest 1 and the zeros below it. Then switch to the XOR example and watch the pairs cancel.

number = 44

00101100

count

count = 0
while number:
number &= number - 1 # clear the lowest 1
count += 1
return count

44 is 101100 in binary. Count its 1 bits without looking at every position.

1 / 8

Why does number & (number - 1) work? Subtracting 1 turns the lowest 1 into a 0, and the zeros below it into ones, like 100 - 1 = 099 in decimal. The bits above it don’t change. AND keeps a bit only where both are 1. So the bits above stay, and the lowest 1 and everything below it become 0. The loop runs once per 1 bit, not once per position.

The template

Count 1 bits, find the single number with XOR, and count the bits of every number from 0 to n (limit in code):

BitManipulation.javaexample.pyBitManipulation.csmain.goexample.ts

import java.util.Arrays;

public class BitManipulation {
    static int hammingWeight(int number) {
        // Count the 1 bits. number & (number - 1) clears the lowest 1 bit, so the loop runs once
        // per 1 bit, not once per bit position. O(number of 1 bits) time, O(1) memory. number != 0
        // (not number > 0) so a negative int, whose top bit is 1, works too.
        int count = 0;
        while (number != 0) {
            // number - 1 flips the lowest 1 and the 0s below it; & keeps the bits above
            number &= number - 1;
            count++;
        }
        return count;
    }

    static int singleNumber(int[] nums) {
        // The number that appears once, when every other number appears twice. number ^ number is 0
        // and number ^ 0 is number, and XOR doesn't care about order, so every pair cancels. O(n)
        // time for n numbers, O(1) memory.
        int xorTotal = 0;
        for (int number : nums) xorTotal ^= number;
        return xorTotal;
    }

    static int[] countBits(int limit) {
        // 1 bits of every number from 0 to limit (n in the Big O). i >> 1 is i without its last
        // bit, and that answer is already known, so each number costs O(1). O(n) time in total.
        int[] bits = new int[limit + 1];
        for (int i = 1; i <= limit; i++) bits[i] = bits[i >> 1] + (i & 1);
        return bits;
    }

    public static void main(String[] args) {
        check(hammingWeight(44) == 3); // 101100
        check(hammingWeight(0) == 0);
        check(hammingWeight(Integer.MAX_VALUE) == 31);
        check(hammingWeight(-1) == 32); // all 32 bits set
        check(singleNumber(new int[] {4, 1, 2, 1, 2}) == 4);
        check(singleNumber(new int[] {7}) == 7);
        check(Arrays.equals(countBits(5), new int[] {0, 1, 1, 2, 1, 2}));
        check(Arrays.equals(countBits(0), new int[] {0}));
        System.out.println("ok: hammingWeight, singleNumber and countBits");
    }

    static void check(boolean ok) {
        if (!ok) throw new AssertionError();
    }
}

count_bits is a tiny dynamic program. The number i has the same bits as i >> 1, which drops its last bit, plus that last bit. The smaller number’s answer is already in the list, so each step is O(1).

Variations

Missing number

The numbers 0 to n are in the list (n is len(nums)), except one. XOR every index from 0 to n together with every value. Each number that is present appears twice, once as an index and once as a value, so it cancels. Only the missing one is left. The sum formula n(n + 1)/2 - sum also works. XOR can’t overflow, which matters in languages with fixed-size integers.

Add without +

XOR adds two numbers but drops every carry: 1 + 1 gives 0. AND finds the positions where both bits are 1, which are exactly the carries. Shift the carries left by one, since a carry goes to the next position. Then add them again the same way. Repeat until there’s no carry. In Python, mask every step with 0xFFFFFFFF to act like 32 bits, and turn the result back into a negative number if bit 31 is set. Otherwise a negative input loops forever.

Subsets as bitmasks

With n items, every number from 0 to 2**n - 1 is one subset: bit i says whether item i is in it. Looping over those numbers lists every subset with no recursion. Bitmasks also work as compact “seen” sets. With only 26 letters, a word’s set of letters fits in one int, and two words share no letter when mask_a & mask_b == 0.

Reverse bits

Take bits from the input one at a time, starting at the right. Each time, shift the output left by one and add the bit. After 32 rounds, the first bit read is at the far left. Loop exactly 32 times, not until the input is 0. The input’s leading zeros must become the output’s trailing zeros. And in Java, >> on a negative input copies the sign bit, so the input would never reach 0.

Complexity

	Time	Extra memory
Read, set, clear or flip one bit	O(1)	O(1)
Count 1 bits with `number & (number - 1)`	O(number of 1 bits)	O(1)
Count or reverse every bit	O(32) per int	O(1)
Single or missing number by XOR	O(n)	O(1)
Every subset of n items by mask	O(2ⁿ · n)	O(1) per mask

Say this out loud

XOR of a number with itself is 0, and XOR with 0 changes nothing. So if I XOR everything together, every pair cancels and the single number is left. That’s O(n) time and O(1) memory, with no hash set.

Interview questions

Interviewer asksHow do you check whether a number is a power of two in O(1)?

A power of two has exactly one 1 bit. number & (number - 1) clears the lowest 1, so for a power of two it leaves 0. Check number > 0 too, since 0 also gives 0 and isn’t a power of two. In Java with a negative int, number > 0 also rules out the minimum value, which has one bit set but is negative.

Interviewer asksEvery number appears three times except one. Does XOR still work?

Not directly, because three copies XOR to the number itself, not 0. Count bits instead. For each of the 32 positions, add up that bit over all numbers and take the sum modulo 3. What is left is the single number’s bit. That’s O(32 · n) time and O(1) memory.

Interviewer asksWhy use XOR for the missing number when the sum formula is simpler?

The sum of 0 to n grows as n², so in a 32-bit int it overflows once n is above about 65,000. Java and C# wrap around without an error, and the answer happens to stay right because the wrap cancels. But that is hard to argue in an interview. XOR never leaves the range of its inputs, so there is nothing to argue.

Practice

10 problems on LeetCode: 7 easy, 3 medium

Ticks are saved in this browser only. Clear your site data and they're gone.

Five of these are solved step by step on this site, as part of the Blind 75: Number of 1 Bits, Counting Bits, Missing Number, Reverse Bits and Sum of Two Integers.

Recap

Use it when the question names bits, says “without + or extra memory”, or has pairs to cancel, or a set small enough to fit in one integer.
One bit: read with >> and & 1, set with |, clear with & ~, flip with ^.
number & (number - 1) clears the lowest 1. XOR cancels pairs.
Cost: O(1) per operation, so most answers are O(n) time and O(1) memory.
Watch for: the sign bit, >> versus >>>, and Python’s integers with no fixed width.