Bit Manipulation

1The five bitwise operators

Bitwise operators act on each bit of an integer. AND (\&) keeps a bit only when both sides have it — the classic mask. OR (|) turns bits on. XOR (\oplus) flips a bit where the other side is 1, so it toggles and also surfaces differences. NOT (\sim) flips every bit. Shifts move the bit pattern: left shift multiplies a non-negative n by a power of two, and arithmetic-style right shift floors a non-negative n by a power of two.

These are not Boolean short-circuit operators. They rewrite the binary representation in place, which is why masks, flags, and compact set encodings all start here.

Figure. Five operators, five jobs: mask, combine, toggle/cancel, invert, and shift — do not treat them as interchangeable.

Pick the operator by job

1. Mask or intersectUse AND with a mask whose 1-bits mark the positions you care about.
2. Turn bits onUse OR with a mask that has 1s only in the positions to set.
3. Toggle or differUse XOR to flip selected bits, or to cancel equal values later.
4. Scale by 2^kUse n \ll k or n \gg k on non-negative n instead of multiplying or dividing by 2^k.

2XOR cancel: find the unpaired number

XOR has two identities that make pair cancellation free: x \oplus x = 0 and x \oplus 0 = x. Folding XOR across an array therefore erases every value that appears an even number of times and leaves a value that appears once. That is the classic Single Number interview pattern — O(n) time and O(1) extra space, with no hash map.

Order does not matter: XOR is associative and commutative, so any traversal order yields the same accumulator.

Figure. XOR cancels pairs: a\oplus a=0, so a fold over a duplicated multiset leaves the singleton.

How the accumulator collapses

1. Start at 0result = 0. XOR with 0 leaves the first value unchanged when it arrives.
2. Fold every elementresult = result \oplus nums[i] for each index.
3. Pairs vanishEach duplicated value meets itself in the fold and becomes 0; the unpaired value remains.

Single Number

def single_number(nums):
    result = 0
    for x in nums:
        result ^= x
    return result

3Test, set, and clear bit i

Bit index i counts from the least-significant bit as 0. Test bit i with (n \gg i) \& 1. Set it with n | (1 \ll i). Clear it with n \& \sim(1 \ll i) — the inverted one-hot mask keeps every bit except i.

The one-hot 1 \ll i is the whole trick: build a mask with a single 1, then AND, OR, or AND-NOT against n. Getting the index off-by-one is the usual bug — index zero is the units bit, not the leftmost drawn digit.

Figure. Four cells show 1101_2 = 13. Index i grows right-to-left from the least-significant bit; bit 1 is the 0 cell.

Three masks from one-hot

1. Build 1 \ll iA mask with only bit i set.
2. TestShift n down by i and AND with 1 — result is 0 or 1.
3. Set or clearOR with the one-hot to set; AND with its NOT to clear.

4Power-of-two test

A positive integer n is a power of two if and only if it has exactly one bit set. Clearing the lowest set bit with n \& (n - 1) therefore yields 0 exactly on those values: the single 1 disappears and nothing remains. The full test is n > 0 and n \& (n - 1) = 0 — without the positivity check, zero falsely looks like a power of two.

That is why the identity shows up in allocator alignment checks and in "is this length a power of two?" interview prompts.

Figure. A power of two is a single 1 among zeros. Clearing that 1 with n \& (n-1) leaves an all-zero word.

Apply the test

1. Reject non-positiveIf n \le 0, it is not a power of two.
2. Clear lowest 1Compute n \& (n - 1). Subtracting 1 flips the trailing 0s and the lowest 1.
3. Demand zeroIf the result is 0, the original n had exactly one set bit.

5Clear or isolate the lowest set bit

Two identities manipulate the least-significant 1 without scanning all bits. n \& (n - 1) clears that lowest set bit and leaves every higher bit unchanged. n \& (-n) isolates it — on two's-complement integers the negation flips bits above the lowest 1, so the AND keeps only that one-hot value.

Clearing is the engine inside Brian Kernighan's popcount; isolating is the engine inside "rightmost flag" loops and some Fenwick-tree index steps.

Figure. Three rows for n = 12 (1100_2): source, clear-lowest (1000_2 = 8), and isolate-lowest (0100_2 = 4). Clear removes the bit from n; isolate extracts it as a one-hot mask.

Same n, two results

1. Clearn \& (n - 1) turns the lowest 1 into 0.
2. Isolaten \& (-n) returns a value with only that lowest 1 set.
3. Do not confuse themClear removes the bit from n; isolate extracts the bit as its own mask.

6Count set bits in O(popcount)

Brian Kernighan's loop counts 1-bits by repeatedly clearing the lowest set bit: while n \neq 0, do n \&= (n - 1) and increment a counter. Each iteration removes exactly one 1, so the loop runs once per set bit — O(\mathrm{popcount}(n)), not O(32) or O(64) for a fixed word width.

When the density of 1s is low, that beats scanning every bit position. Hardware `popcount` instructions are faster still when available; the loop is the portable interview form of the same idea.

Reuse the clear-lowest strip from Clear or isolate the lowest set bit: each x\ &=\ x-1 clears one set bit; the loop count equals the popcount.

Walk the 1s

1. Count at 0Initialize count = 0.
2. Clear lowest 1Replace n with n \& (n - 1) and add 1 to count.
3. Stop at 0When n becomes 0 every set bit has been removed; return count.

Brian Kernighan popcount

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

7Bitmasks as subsets

A bitmask packs a subset of up to about 32 or 64 indexed elements into one integer: each bit flags whether that index is in the subset. Membership is (mask \gg i) \& 1. Union is OR, intersection is AND, and symmetric difference is XOR — each O(1) on a machine word.

That encoding is why subset DP and many combinatorial searches store state as an integer rather than as a hash set of indices.

Figure. Three cells for a 3-element universe. Mask 0b101 has item 0 and item 2 in the subset; item 1 is absent.

Set algebra on bits

1. EncodeTurn membership of index i into bit i of an integer mask.
2. CombineUnion |, intersection \&, toggle membership with XOR against 1 \ll i.
3. QueryTest bit i for membership in O(1).

8Enumerate masks: subset DP shape

Once subsets are integers from 0 to 2^n - 1, many DP transitions scan every mask and every element: for mask in 0 \ldots 2^n - 1, for i in 0 \ldots n - 1, update a state from mask with bit i flipped on or off. That double loop is the standard subset-DP budget — exponential in n, times a linear scan of bit positions — when n is about 20 or less.

The bit encoding is what makes the outer index a contiguous integer range. Without masks you would hash sets; with masks the array dp[1 \ll n] is enough.

Figure. For n=3 the outer index is the eight masks 0…7. On the current mask the inner loop visits each of the n bit positions — here three visits under mask 5. Interview n near 20 is the same shape, not a longer row.

The O(2^n n) skeleton

1. Allocate by maskIndex DP by the integer mask, size 2^n.
2. Scan masksIterate mask from 0 to 2^n - 1 (often in an order that respects transitions).
3. Try each bitFor each i, read or write the neighbour mask with bit i changed — n work per mask.

Scan all masks and bits

def for_each_mask_bit(n, visit):
    for mask in range(1 << n):
        for i in range(n):
            visit(mask, i, (mask >> i) & 1)