Bit manipulation

Problem

Bit questions usually say so: count the 1 bits, reverse the bits, add two numbers without using +. Others hide it: find the one value that appears once when every other value appears twice, find the missing number with O(1) extra space, or build the smallest numbers that all share a set of bits. The giveaway is a demand for constant space on a problem that would otherwise need a hash set, or a statement phrased in terms of "AND", "OR", "XOR" or powers of two. The pattern is to reason about each bit position independently and pick the operator whose truth table does the job.

Intuition

Think of each bit position as its own tiny problem. AND keeps a bit only where both inputs have it, OR keeps it where either has it, and XOR keeps it where exactly one has it, which makes XOR "addition with no carry" and also "toggle". Because XOR undoes itself, XORing a list in which every value appears twice leaves zero in every position, and adding one extra value leaves exactly that value.

The other workhorse is what subtracting one does to a binary number: the lowest 1 becomes 0 and every 0 below it becomes 1. The bits above are untouched. So n and n - 1 agree above the lowest 1 and disagree from it downwards, and their AND is n with its lowest 1 switched off. Counting how many times you can do that before reaching zero counts the 1 bits, and the loop runs once per 1 rather than once per position.

Green bits are set; amber marks the lowest set bit, the one n & (n - 1) removes. The loop never visits the zero positions.

Mechanics

The operators and their identities

• x ^ x == 0, x ^ 0 == x, and XOR is associative and commutative: order does not matter, pairs cancel.
• x & (x - 1) clears the lowest set bit; it is zero exactly when x is zero or a power of two.
• x & -x isolates the lowest set bit, because −x in two's complement is ~x + 1.
• x >> k & 1 reads bit k; x | 1 << k sets it; x & ~(1 << k) clears it; x ^ 1 << k toggles it.
• x >> 1 is x // 2 and x << 1 is 2 * x for non-negative x.

Cancelling pairs

Invariant for Single Number: after reading a prefix, the accumulator is the XOR of the values that have appeared an odd number of times in it. At the end only the lone value is odd. Missing Number is the same trick with a second list: XOR every index 0 to n with every value, and each present number cancels against its index, leaving the one index with no partner.

Counting bits for every i

The bits of i are the bits of i >> 1 followed by one more bit, i & 1. Since i >> 1 < i for every positive i, filling the table in increasing order means the smaller entry is always ready, which is a one-line DP over O(n) states. bits[i] = bits[i & (i - 1)] + 1 works for the same reason, dropping the lowest 1 instead of the lowest bit.

Adding with XOR and AND

In a single column, the sum bit of two bits is their XOR and the carry is their AND. Doing every column at once, a ^ b is the sum ignoring carries and (a & b) << 1 is every carry moved to the column it lands in. Their true sum equals the original a + b, so repeat with that pair until the carry is zero. Each round, the carry's lowest set bit moves at least one place left, so a 32-bit sum needs at most 32 rounds. Python complicates this: its integers have no width, so a negative carry would shift left forever. Mask every value to 32 bits with 0xFFFFFFFF, then read a result above 231 − 1 back as negative by subtracting 2³².

Each column is one round. The next round's a and b are this round's green sum and amber carry. The diagram scrolls sideways on a narrow screen.

Common prefixes and free bits

The AND of every number from left to right keeps a bit only if no number in the range has a 0 there. Below the highest bit where left and right differ, the range crosses a point where that low block rolls over from all ones to all zeros, so every lower bit is 0 somewhere. What survives is the common binary prefix: shift both right until they are equal, then shift back. Minimum Array End runs the other way. Every element must contain all of x's bits, so the valid values are x with some pattern written into its zero positions, and those patterns, read in order, are just 0, 1, 2, … Writing n − 1 into the zero bits of x gives the n-th smallest valid value.

Worked example

Single Number on [4, 1, 2, 1, 2].

The 1s and 2s cancel and the accumulator ends at 4.

Number of 1 Bits, n = 44. The table repeats the first diagram.

3 steps, so 44 has 3 one bits.

Counting Bits for 0 to 8.

Sum of Two Integers, 5 + 3 and −2 + 3.

The answer is 8. For −2 + 3 the masked −2 is 4294967294; the carry walks all the way out of the 32-bit window in 31 rounds and the result reads back as 1.

Bitwise AND of 9 through 12.

The common prefix is 1 after 3 shifts, so the AND is 1 << 3 = 8.

Minimum Array End, n = 3, x = 4 (100). The third valid value writes n − 1 = 2 = 10 into x's zero bits: bit 0 gets 0, bit 1 gets 1, giving 110 = 6, so the array is 4, 5, 6. Two smaller checks: Missing Number on [3, 0, 1] gives 2, and Add Binary on "1011" and "111" gives "10010".

Implementation

def single_number(nums):
    acc = 0
    for value in nums:
        acc ^= value
    return acc


def hamming_weight(n):
    count = 0
    while n:
        n &= n - 1
        count += 1
    return count


def count_bits(n):
    bits = [0] * (n + 1)
    for i in range(1, n + 1):
        bits[i] = bits[i >> 1] + (i & 1)
    return bits

Variations and edge cases

MASK = 0xFFFFFFFF


def get_sum(a, b):
    a, b = a & MASK, b & MASK
    while b:
        a, b = a ^ b, (a & b) << 1 & MASK
    return a if a <= 0x7FFFFFFF else a - (1 << 32)    # read bit 31 as the sign


def reverse_bits(n):
    result = 0
    for _ in range(32):
        result = result << 1 | n & 1
        n >>= 1
    return result


def range_bitwise_and(left, right):
    shift = 0
    while left != right:
        left, right, shift = left >> 1, right >> 1, shift + 1
    return left << shift


def min_end(n, x):
    result, k, bit = x, n - 1, 1
    while k:
        if not x & bit:
            if k & 1:
                result |= bit
            k >>= 1
        bit <<= 1
    return result

• Operator precedence. In Python, + and - bind tighter than shifts, which bind tighter than &, then ^, then |, so 1 << n - 1 is 1 << (n - 1). Comparisons bind looser than all of them, so x & 1 == 0 works in Python but not in C or Java, where it parses as x & (1 == 0). Parentheses cost nothing.
• Negative numbers. Python's -1 >> 1 is −1 forever, and bin(-5) is '-0b101', not two's complement. Mask with 0xFFFFFFFF whenever a problem means 32-bit unsigned.
• Fixed width. Reverse Bits must loop exactly 32 times, even after n becomes zero, or leading zeros of the input are lost from the end of the output.
• Built-ins. int.bit_count() (Python 3.10+) and bin(n).count("1") count bits; n.bit_length() gives the position of the highest 1. Say you know them, then show the loop.

Complexity and tradeoffs

• XOR folds are O(n) time and O(1) space; the hash-set alternative is also O(n) time but O(n) space, which is exactly what Single Number rules out.
• Popcount with n & (n - 1) is O(number of 1 bits), at most 32 for a 32-bit integer; checking every position is always 32. Both are O(1) for fixed width.
• Counting Bits is O(n) for the whole table, against O(n log n) for popcounting each i separately.
• Add without plus takes at most 32 rounds, since the carry's lowest bit moves left each round.
• Range AND is O(log right), not O(right − left), and Minimum Array End is O(log n + log x) where the naive search through supersets of x is O(n).
• When it is the wrong tool. Missing Number is just as clear with the sum formula from number math. Bitmask enumeration of subsets is O(2ⁿ · n) and only fits n up to about 20; past that, prune with backtracking. Readability matters: a trick an interviewer has to decode is worth a sentence of explanation.

Problems

Do Single Number, Number of 1 Bits and Counting Bits first; they are the three identities in their purest form. Then Missing Number two ways, Reverse Bits for fixed-width care, and Sum of Two Integers last, because Python's unbounded integers make the masking the real lesson.

Easy

• 67. Add Binary Grind 169 NeetCode 250
  Add the strings from right to left with a carry, the same column-by-column addition as with decimal digits but in base two.
• 136. Single Number Grind 169 NeetCode 150 NeetCode 250
  XOR every number together: equal pairs cancel to zero, leaving the one that appears once.
• 190. Reverse Bits Blind 75 Grind 169 NeetCode 150 NeetCode 250
  Shift bits out of the input from the right and into the result from the left, 32 times.
• 191. Number of 1 Bits Blind 75 Grind 169 NeetCode 150 NeetCode 250
  n & (n-1) clears the lowest set bit, so count how many times that runs before n reaches zero.
• 268. Missing Number Blind 75 Grind 169 NeetCode 150 NeetCode 250
  XOR all indices 0..n with all values, or subtract the array's sum from n(n+1)/2; either way the missing number is what is left.
• 338. Counting Bits Blind 75 Grind 169 NeetCode 150 NeetCode 250
  The bit count of i is the count of i shifted right by one, plus the lowest bit of i.

Medium

• 201. Bitwise AND of Numbers Range NeetCode 250
  The AND over a range keeps only the common binary prefix of its two ends, so shift both right until they are equal.
• 371. Sum of Two Integers Blind 75 NeetCode 150 NeetCode 250
  XOR adds without carrying and AND shifted left gives the carries, so repeat until there are no carries, masking to 32 bits in Python.
• 3133. Minimum Array End NeetCode 250
  Every element must contain x's set bits, so write n-1 in binary into the zero bit positions of x.

Also uses this pattern

These problems have a different home page, but this idea is part of their solution.

• 1863. Sum of All Subset XOR Totals Easy
• 78. Subsets Medium

Connections

Bits are base-two digits, so everything on number math carries over: Add Binary is the decimal carry loop in base two, and square-and-multiply reads the exponent's bits. Bitmasks enumerate the subsets that backtracking builds by recursion, and a set packed into an integer is the state of bitmask DP. Counting Bits is a reminder that DP does not need a grid, just a smaller answer you already have.

Check yourself

References

• Warren, H. S., Hacker's Delight, 2nd edition, chapter 2 (basics: turning off the rightmost 1 bit, isolating it) and chapter 5 (counting bits).
• Knuth, D. E., The Art of Computer Programming, volume 4A, section 7.1.3, "Bitwise tricks and techniques".
• Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, 3rd edition, problem 17-1 (the bit-reversed binary counter).
• Skiena, S., The Algorithm Design Manual, section 14.5, on generating subsets with bitmasks.
• Sedgewick and Wayne, Algorithms, section 1.1, on primitive integer types and their ranges.
• The NeetCode roadmap and the Blind 75, Grind 169, NeetCode 150 and NeetCode 250 lists, used as the index of topics and problems.