Bit operations cookbook

Two expressions carry this chapter:

x & -x         # the value of the lowest set bit
x & (x - 1)    # x with the lowest set bit cleared

Everything else in Part 11 is built on those two lines. Fenwick trees walk the index space with i += i & -i. Brian Kernighan's popcount loops on n &= n - 1. Bitmask DP iterates subsets with sub = (sub - 1) & mask. The single-number-XOR family separates two unique numbers by isolating any one bit they differ in — and that bit is (a ^ b) & -(a ^ b). Memorize both identities and the rest of Part 11 stops looking like sorcery.

The other primitives (set, clear, flip, test, popcount, iterate set bits) are one line apiece. This chapter is a reference, not a narrative. Skim it once. Come back when a problem asks for one of the operations and you forgot the exact form.

The bit manipulation primer introduced AND, OR, XOR, NOT, shifts, and Brian Kernighan's loop. This chapter is the operational vocabulary on top of those primitives, the one Hacker's Delight §2-1 catalogs and that JDK source comments tag with // HD, Section 2-1.^[1]

Set bit i#

x | (1 << i)

1 << i is a mask with one bit set at position i. OR with that mask forces bit i to 1 and leaves every other bit alone. Idempotent: setting a bit that's already set is a no-op.

def set_bit(x, i):
    return x | (1 << i)

Clear bit i#

x & ~(1 << i)

Negate the single-bit mask to get all-ones-except-position-i. AND clears bit i and leaves the rest. Also idempotent.

Go has a single operator for this combination: x &^ (1 << i) reads as "x AND NOT (1 << i)" and saves one token.

def clear_bit(x, i):
    return x & ~(1 << i)

Flip bit i#

x ^ (1 << i)

XOR with the mask flips the target bit, leaves the others. Two flips return to the original — XOR is its own inverse, the foundational identity for everything in chapter 11.1.

def flip_bit(x, i):
    return x ^ (1 << i)

Test bit i#

(x >> i) & 1     # returns 0 or 1

Shift bit i down to position 0, then mask off everything else. The parentheses are not optional. x >> i & 1 happens to parse correctly in C, C++, Java, and Python (>> binds tighter than &), but reviewers will flag it every time, and one day you'll write the same expression with == in it and get bitten by == binding tighter than &. Parenthesize.

def test_bit(x, i):
    return (x >> i) & 1

Isolate the lowest set bit: x & -x#

The first of the two load-bearing identities. Returns a power of two: the value of the lowest set bit of x, or zero if x is zero.

The proof is two's complement.^[2] By definition -x = ~x + 1. Flipping every bit of x produces ~x, where the trailing ones cover the positions that were trailing zeros in x. Adding one to ~x propagates a carry through that run of trailing ones, rolling them back to zero and stopping at the first zero in ~x. That stopping position is exactly the lowest 1-bit of x, and it now holds a 1 in both x and -x. Every other bit position holds a 1 in exactly one of the two operands. AND keeps only the shared bit.

Walk it on x = 0b01100 (= 12):

 x = 01100
~x = 10011
-x = 10100   (~x + 1, the carry hits position 2)
x & -x       = 00100   (only position 2 is set in both)

Position 2 is the lowest set bit of 12. The result is 4 = 2^2, a power of two: the value of that bit, not its index.

def lowest_set_bit(x):
    return x & -x

This is the operation Fenwick trees use for index walks: update(i, v) advances by i += i & -i, query(i) retreats by i -= i & -i. The walk costs O(log n) per operation because every step strips the lowest set bit, and there are at most log2(n) of them.

Strip the lowest set bit: x & (x - 1)#

The second load-bearing identity. Returns x with the lowest set bit removed, leaving every bit above untouched.

Subtracting one from x borrows through the trailing zeros of x, flipping them to ones. The borrow stops at the lowest set bit of x, which becomes a zero. So x - 1 and x agree above the lowest set bit, disagree at the lowest set bit (1 in x, 0 in x - 1), and disagree below (0 in x, 1 in x - 1). AND keeps the agreeing high bits and zeros the rest.

Same x = 0b01100:

x     = 01100
x - 1 = 01011    (borrow rolls through positions 0 and 1)
x & (x - 1) = 01000   (positions 3 above; lowest 1 at position 2 is gone)

Twelve loses its lowest set bit and becomes eight.

def strip_lowest_set_bit(x):
    return x & (x - 1)

The mnemonic that keeps the two identities straight: minus-x isolates, x-minus-one strips. They look symmetric. They are not. x & -x returns the bit's value; x & (x - 1) returns the integer with that bit removed. Submissions on LC 191 and LC 338 routinely swap the two and infinite-loop or return the wrong count. Build the muscle memory before you trust it.

The corollary: x & (x - 1) == 0 is true iff x is a power of two (assuming x > 0). A power of two has exactly one set bit; stripping it leaves zero. Anything else has at least two set bits, and stripping the lowest leaves something nonzero.

Count set bits: Brian Kernighan's loop#

The signature application of x & (x - 1). Strip the lowest set bit until x is zero; count the iterations.

def popcount(x):
    count = 0
    while x:
        x &= x - 1     # one set bit gone per iteration
        count += 1
    return count

Every iteration clears exactly one set bit and never sets one. The loop runs once per set bit, then terminates. On x = 0xFFFFFFFF (all 32 bits set) it runs 32 times. On x = 1 it runs once. The naive for k in range(32): count += (x >> k) & 1 always runs 32 times regardless of input.

Hand-trace on x = 0b1011 (= 11):

Loop exits, returns 3.

The algorithm was first published by Peter Wegner in CACM Vol 3 (1960), independently rediscovered by Derrick Lehmer in 1964, and included as exercise 2-9 in The C Programming Language 2nd edition (1988), which is why the algorithm carries Kernighan's name.^[1:1][3]

The signature problem is LC 338 Counting Bits. Asked to compute popcount for every integer in [0, n], the natural recurrence falls out of x & (x - 1):

# LC 338. Counting Bits


def count_bits(n: int) -> list[int]:
    """Return ans[i] = popcount(i) for i in 0..n.

    Recurrence: dp[i] = dp[i & (i - 1)] + 1.
    Cleared-lowest-bit subproblem already solved; add one for the bit just removed.
    O(n) time, O(n) space (output dominates).
    """
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        dp[i] = dp[i & (i - 1)] + 1
    return dp

// LC 338. Counting Bits

class Sol {
    public int[] countBits(int n) {
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i & (i - 1)] + 1;
        }
        return dp;
    }
}

// LC 338. Counting Bits

#include <vector>

class Sol {
public:
    std::vector<int> countBits(int n) {
        std::vector<int> dp(n + 1, 0);
        for (int i = 1; i <= n; ++i) {
            dp[i] = dp[i & (i - 1)] + 1;
        }
        return dp;
    }
};

// LC 338. Counting Bits

package main

func countBits(n int) []int {
	dp := make([]int, n+1)
	for i := 1; i <= n; i++ {
		dp[i] = dp[i&(i-1)] + 1
	}
	return dp
}

The subproblem dp[i & (i - 1)] is popcount of i with the lowest bit stripped, already computed because i & (i - 1) < i. Add one for the bit just removed. Two lines, O(n) time.

Stdlib popcount: when the loop is the wrong answer#

Don't write Brian Kernighan's loop in production. Every modern language ships a popcount intrinsic that compiles to a hardware POPCNT instruction on x86 SSE4.2 and ARMv8.^[4]

Three things are happening in the background that the loop hides. The SWAR algorithm (SIMD Within A Register) uses magic constants 0x55555555, 0x33333333, 0x0F0F0F0F to count bits in parallel across nibbles, bytes, and halves of the word in O(log w) operations on a w-bit word. JDK's Integer.bitCount is exactly this construction; the source is short enough to read in one minute and is the cleanest production reference for the technique.^[1:3] The hardware POPCNT instruction goes one step further and runs in fixed three-cycle latency regardless of input. And the lookup-table approach pre-computes popcount for every 8-bit byte, then sums four lookups for a 32-bit word: the right tool when you want predictable cache behavior more than peak throughput.

The Brian Kernighan loop wins exactly one teaching round: it makes the proof obvious that the answer is popcount(x). Use it to learn. Use the intrinsic to ship.

Iterate over set bits#

When a problem asks for "every set bit of x," the natural loop combines both identities:

def set_bit_positions(x):
    while x:
        bit = x & -x        # value of the lowest set bit
        x &= x - 1          # strip it; the rest of the loop sees the next-lowest
        yield bit.bit_length() - 1   # convert value to position

For each iteration: isolate the lowest set bit (its value is a power of two), do whatever the problem wants with that position, then strip it. The loop runs popcount(x) times. This is the underlying machinery for bitmask iteration over a set's elements: enumerating subsets of a mask uses the same shape with one twist (sub = (sub - 1) & mask) to walk subsets in a fixed order rather than just the set bits of one mask. Subset enumeration with bitmasks makes that twist load-bearing.

Stdlib position-of-lowest-set-bit calls exist when you don't want to hand-convert value to position: Java Integer.numberOfTrailingZeros(x), C++20 std::countr_zero(x), Go bits.TrailingZeros(x), Python (x & -x).bit_length() - 1 (no direct intrinsic; bigint friendly). All four return a defined value when x = 0: 32 (Java), w (C++/Go for width-w types), undefined for the Python expression (returns -1 because (0).bit_length() == 0). Range-check first.

Operator precedence and language-shift gotchas#

Bit operators have lower precedence than comparisons in C, C++, Java, and Python. x & 1 == 0 parses as x & (1 == 0) = x & 0 = 0, which is falsy in every language. The condition is never true. Parenthesize: (x & 1) == 0. GCC's -Wparentheses was added specifically for this antipattern, and the warning fires on the same expression every interview season.

Three more cross-language traps for the cookbook reader.

The fifth trap is the off-by-one in same-width mask construction. For LC 1009 Complement of Base 10 Integer with n = 5 (0b101), the same-width all-ones mask is 0b111 = 7, not 0b1111 = 15. The iterative builder is harder to get wrong than the closed form: mask = 1; while mask < n: mask = (mask << 1) | 1. After the loop mask >= n and mask is 0b1...1 with the same bit count as n. Then complement = mask ^ n.

Practice#

This chapter teaches reference primitives; the ladder pulls problems where the cookbook is the solution. The earlier popcount and Hamming-distance problems (LC 191, LC 461) live in the bit manipulation primer and don't repeat here.

CORE#

• LC 338 — Counting Bits [Easy] • bit-dp-on-low-bit ★
• LC 1009 — Complement of Base 10 Integer [Easy] • mask-construction (reference: Python only)
• LC 201 — Bitwise AND of Numbers Range [Medium] • common-prefix-via-shift (reference: Python only)

STRETCH#

• LC 89 — Gray Code [Medium] • gray-code-formula (reference: Python only)
• LC 1521 — Find a Value of a Mysterious Function Closest to Target [Hard] • sliding-and-deduplication (reference: Python only)

LC 1521 is the rare canonical Hard for the per-bit-monotonicity argument: each AND-of-subarray-ending-here can only clear bits, never set them, so the set of distinct AND-values you carry forward has size at most log2(max(arr)) + 1. Pure cookbook reasoning at scale.

Where this leads#

XOR patterns takes the cancellation identity (a ^ a = 0) and builds the single-number family on top of it, using x & -x as the bit-isolator that splits two unique numbers into two groups. Subset enumeration with bitmasks iterates the set bits of a mask using the loop in this chapter's "Iterate over set bits" section. And bitmask DP uses the same iteration shape for state transitions over O(2^n) subset states.

Outside Part 11, the cookbook's identities show up everywhere. Fenwick trees walk indices with i += i & -i. The JDK HashMap rounds capacity up to a power of two with Integer.numberOfLeadingZeros and the strip-lowest-bit identity. Binary search uses unsigned right shift to compute a midpoint without overflow: lo + ((hi - lo) >>> 1) in Java, the same logic everywhere else.

XOR patterns is next.

References#