Bit Manipulation: Core Tricks and Interview Patterns

1. Introduction and Motivation

A computer stores every integer as a fixed-width sequence of bits, and the bitwise operators &, |, ^, ~, <<, and >> manipulate that sequence directly, without the loops or conditionals that operate on the value's decimal meaning. Because these operators run in a single CPU cycle and touch all bits of a word at once, they let a handful of short expressions replace what would otherwise be a loop over individual bits.

Interview problems reuse a small, fixed set of these expressions: testing whether a number is a power of two, counting how many bits are set, isolating the lowest set bit, finding a value that appears an odd number of times, or representing a subset of a small set as a single integer. None of these tricks require new algorithmic ideas once you can read binary arithmetic fluently; they require recognizing which pattern a problem is quietly asking for.

2. Prerequisites

This lesson assumes only that you can convert a small integer to and from its binary representation and that you know two's-complement integers represent negative numbers by inverting and adding one, which is why -n and ~n + 1 are the same value. No other lesson on this site is strictly required first, but pairing this lesson with Algorithm Analysis: Correctness & Complexity is useful for framing why "one operation per bit" is a meaningful complexity bound rather than just a folk claim.

3. A Concrete Example

The loop stops the moment n reaches zero, which happens after exactly as many iterations as there are set bits. The trace never inspects a bit that is already zero, which is the property that separates this trick from a naive bit-by-bit scan.

4. Core Insight

1. Start a counter at zero.
2. While n is not zero, replace n with n & (n - 1).
3. Increment the counter once per replacement.
4. Return the counter once n becomes zero; it equals the number of set bits, the population count or "popcount" of the original value.

5. Correctness: Why It Works

Write n in binary and let position $k$ be its lowest set bit, so every bit below $k$ is zero. Subtracting 1 borrows through those zero bits: positions below $k$ flip from 0 to 1, position $k$ flips from 1 to 0, and every bit above $k$ is unchanged. ANDing the original n with this n - 1 keeps only positions where both operands are 1. Above $k$ the two operands are identical, so those bits survive; at $k$ the original has 1 but n - 1 has 0, so that bit is cleared; below $k$ the original was already 0, so the result stays 0. The net effect is: one specific 1-bit disappears, nothing else changes.

Because each iteration clears exactly one set bit and never sets a new one, n strictly decreases and the number of set bits strictly decreases by exactly one per iteration. The loop must therefore terminate, and it terminates after precisely $\text{popcount}(n)$ iterations, which is the quantity being counted. This is the same invariant-based reasoning as any other loop proof: state what stays true on each pass (the set-bit count drops by one), confirm it starts true, and confirm it forces termination.

6. Complexity Analysis

A naive approach that shifts and tests every bit position always costs $\Theta(b)$ for a $b$-bit word, regardless of how many bits are actually set. Kernighan's trick is never asymptotically worse and is often much faster in practice, which is why it is the standard hand-rolled popcount before reaching for a hardware instruction such as POPCNT or a language built-in such as Python's int.bit_count().

7. Three-Language Implementation

Each panel implements popcount with Kernighan's trick and runs it against the same worked example, 44, printing 3.

def popcount(n):
    if n < 0:
        raise ValueError("popcount expects a non-negative integer")
    count = 0
    while n:
        n &= n - 1
        count += 1
    return count

sample = 44
print("Set bits:", popcount(sample))  # Set bits: 3

#include <cstdint>
#include <iostream>

int popcount(uint32_t n) {
    int count = 0;
    while (n) {
        n &= n - 1;
        ++count;
    }
    return count;
}

int main() {
    uint32_t sample = 44;
    std::cout << "Set bits: " << popcount(sample) << '\n';
}

public class PopCount {
    static int popcount(int n) {
        int count = 0;
        while (n != 0) {
            n &= n - 1;
            count++;
        }
        return count;
    }

    public static void main(String[] args) {
        int sample = 44;
        System.out.println("Set bits: " + popcount(sample)); // Set bits: 3
    }
}

8. Core Bit-Manipulation Patterns

Bit Basics: Set, Clear, Toggle, Test

Four expressions cover almost every single-bit manipulation, where i is a zero-based bit position counted from the least significant bit:

• Set bit i: x | (1 << i) forces that position to 1 and leaves every other bit unchanged.
• Clear bit i: x & ~(1 << i) forces that position to 0 and leaves every other bit unchanged.
• Toggle bit i: x ^ (1 << i) flips that position and leaves every other bit unchanged, because XOR with 0 is identity and XOR with 1 is inversion.
• Test bit i: (x >> i) & 1 shifts the target bit into position 0 and masks off everything else, giving 0 or 1.

Every other trick in this lesson is built out of these four moves, so it is worth being able to write each one from memory before moving on.

Checking Power of Two

A positive integer is a power of two exactly when it has a single set bit, such as 1000 for 8. Kernighan's clearing trick applies directly: clearing the lowest set bit of a power of two must produce zero, because there is no other set bit left. So the one-line test is:

$$n \gt 0 \text{ and } n \mathbin{\&} (n - 1) = 0$$

The n > 0 guard matters because at n = 0, n - 1 underflows to all-ones, and 0 & all-ones is also 0, which would incorrectly classify 0 as a power of two.

Counting Set Bits: Brian Kernighan's Trick

This is the algorithm traced in section 3 and implemented in section 7: repeatedly apply n &= n - 1 and count the iterations. It generalizes the single-bit clear from section "Bit Basics" into a loop that clears one set bit per pass, giving $O(\text{popcount}(n))$ instead of the $O(\text{bits})$ cost of testing every position with the "test bit" expression above.

Lowest Set Bit Isolation

The expression n & -n produces an integer with only the lowest set bit of n turned on and everything else cleared. It works because -n equals ~n + 1 in two's complement, so it flips every bit and adds one; the addition carries through all the trailing zeros of n, reproducing them as zeros in -n, until it reaches the lowest set bit, where the carry stops and that bit stays 1 while every higher bit is inverted relative to n. ANDing the two therefore leaves only that one shared bit.

This isolation is the mechanism behind Fenwick tree ("Binary Indexed Tree") index arithmetic, where moving to a parent or child node means adding or subtracting exactly the lowest set bit. See Union-Find, Trie, Fenwick Tree & Segment Tree Decision Guide for the full data structure built on top of this operation.

XOR Tricks

XOR is its own inverse: a ^ a = 0 and a ^ 0 = a, and XOR is commutative and associative, so the order values are combined in does not matter. Two classic tricks follow directly:

• Single non-duplicate number: if every value in an array appears exactly twice except for one value that appears once, XORing the entire array cancels every paired value to 0 and leaves only the unpaired value, in $O(n)$ time and $O(1)$ extra space.
• Swap without a temporary: a ^= b; b ^= a; a ^= b; swaps a and b using only XOR, because each step is invertible and the sequence reconstructs the other variable's original value from the combined bits.

Gray Code

A Gray code sequence lists all $2^k$ values of $k$ bits so that each consecutive pair differs in exactly one bit. The expression i ^ (i >> 1) converts an ordinary binary counter i into the $i$-th Gray code value directly, with no lookup table and no recursion, because shifting i right by one and XORing it back exposes exactly the bit boundary where the next binary increment would otherwise ripple-carry through multiple positions.

Bitmasks for Subsets

When a problem has a small set of $n$ elements, an integer with $n$ bits can represent any subset: bit $i$ set means "element $i$ is included." All $2^n$ subsets can be enumerated by counting an integer mask from 0 to $2^n - 1$:

n = len(items)
for mask in range(1 << n):
    subset = [items[i] for i in range(n) if (mask >> i) & 1]
    # process subset

Membership tests, unions, and intersections of subsets become the single-bit and combining operations from earlier in this section: testing element i is (mask >> i) & 1, union of two masks is |, and intersection is &. This bitmask-subset technique is used heavily in the Backtracking & Constraint Search lesson for pruning N-Queens, where a bitmask over columns and diagonals lets the search test and place a queen in constant time instead of rescanning the board.

9. Applications and Alternatives

Bit tricks are not always the right tool. When $n$ grows past roughly 20-25 elements, a $2^n$ subset enumeration becomes too slow, and the problem needs meet-in-the-middle, DP with a different state, or pruning rather than a bigger bitmask. When code readability matters more than the last constant factor, an explicit boolean array or a language's built-in bit_count/popcount intrinsic is often the better choice than hand-rolled bit twiddling.

10. Exercises and Mastery

Easy

1. Single Number: given an array where every element appears twice except for one, find that one element using XOR in $O(n)$ time and $O(1)$ extra space.

Medium

1. Counting Bits: for every integer from 0 to $n$, return its popcount. Do it either by applying Kernighan's trick to each value, or by deriving each answer from a smaller one already computed, using the relation $\text{bits}(i) = \text{bits}(i \gg 1) + (i \mathbin{\&} 1)$.

Hard

1. Subsets via bitmask enumeration: given a set of up to 20 distinct elements, generate every subset by counting a mask from 0 to $2^n-1$ and decoding each mask's set bits. Compare this iterative approach against the recursive include/exclude backtracking alternative covered in the Backtracking & Constraint Search lesson, and note when one is preferable to the other.

Review rhythm: tomorrow, rewrite the four single-bit expressions and the power-of-two test from memory; next week, implement Kernighan's popcount and the single-number XOR trick without looking them up; several weeks later, spot a bitmask opportunity in an unrelated problem, such as compact state in a graph search or DP. Finally, teach someone else why n & (n-1) clears exactly one bit.

11. Summary Cheat Sheet

• Set / clear / toggle / test bit i: x | (1<<i), x & ~(1<<i), x ^ (1<<i), (x>>i) & 1.
• Power of two: n > 0 && (n & (n-1)) == 0.
• Popcount via Kernighan: repeat n &= n-1, counting iterations, in $O(\text{popcount}(n))$.
• Lowest set bit: n & -n, the basis of Fenwick tree index arithmetic.
• XOR is self-inverse: cancels duplicates, isolates a single unmatched value, swaps two variables.
• Gray code: i ^ (i >> 1) generates consecutive values differing by one bit.
• Bitmask subsets: an $n$-bit integer represents a subset of $n$ elements; enumerate all $2^n$ subsets by counting the mask from 0 to $2^n-1$.