Bit Manipulation

Bit manipulation looks like a dark art, but it is really just one idea — an integer is a row of bits, and you can poke at them directly — plus a handful of tricks worth memorising. Those tricks turn O(n) counting into O(1) and O(n) space into O(1).

The idea

Every integer is stored as bits. The bitwise operators work on all those bits at once, in a single machine instruction:

• AND (&) — 1 only where both bits are 1. Used to test or clear bits (with a mask).
• OR (|) — 1 where either bit is 1. Used to set bits.
• XOR (^) — 1 where the bits differ. The workhorse: it cancels equal values.
• NOT (~) — flips every bit.
• Shifts (<<, >>) — slide bits left/right; x << k multiplies by 2ᵏ, x >> k divides by 2ᵏ.

The tricks worth memorising

A small vocabulary covers the large majority of bit problems:

x & 1                 # 1 if x is odd, 0 if even  (test the lowest bit)
x & (x - 1)           # clears the LOWEST set bit  → loop to count set bits
x & -x                # isolates the lowest set bit (e.g. 12 -> 4)
x ^ y                 # bits where x and y differ
a ^ a == 0            # XOR cancels a pair
a ^ 0 == a           # XOR with 0 is identity

x | (1 << k)          # set bit k
x & ~(1 << k)         # clear bit k
x ^ (1 << k)          # toggle bit k
(x >> k) & 1          # test bit k
(1 << n) - 1          # an n-bit "all ones" mask

The x & (x-1) trick deserves a special mention: subtracting 1 flips the lowest set bit and everything below it, so AND-ing with the original wipes exactly that lowest set bit. Repeating it until the number is zero counts the set bits in O(number of set bits), not O(32).

Worked example: single number

Every element appears twice except one. XOR the whole array: the pairs cancel to 0, and the survivor is the lone number — O(n) time, O(1) space, no hash set needed.

def single_number(nums):
    r = 0
    for x in nums:
        r ^= x           # pairs cancel, the unique value remains
    return r
# single_number([4,1,2,1,2]) -> 4

Worked example: counting bits 0..n

countBits(n) returns the number of set bits for every value from 0 to n. The recurrence falls straight out of the tricks: bits[i] = bits[i >> 1] + (i & 1) — drop the lowest bit, then add it back if it was 1.

def count_bits(n):
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        dp[i] = dp[i >> 1] + (i & 1)
    return dp
# count_bits(5) -> [0,1,1,2,1,2]

Enumerating subsets with a bitmask

With n items, every integer from 0 to 2ⁿ - 1 is a subset: bit i set means “item i is in”. This is the backbone of bitmask DP and a compact way to generate the power set.

def subsets(nums):
    n = len(nums); res = []
    for mask in range(1 << n):                 # 0 .. 2^n - 1
        res.append([nums[i] for i in range(n) if mask & (1 << i)])
    return res
# subsets([1,2,3]) -> 8 subsets

When to reach for it

Signals in the prompt: “the single / unique number”, “count the bits” or “number of 1s”, “generate all subsets”, “power of two / power of four”, “swap without a temp”, “add without using +”, or a constraint like n ≤ 20 that hints at a 2ⁿ bitmask over items. Any time you need a set of up-to-~32 (or 64) flags packed into one integer, bits are the tool.

Pitfalls

• Python has arbitrary-precision integers. There is no automatic 32-bit wraparound, and ~x gives a negative number. For problems that assume 32-bit math (e.g. Sum of Two Integers, Reverse Bits), mask with & 0xFFFFFFFF and convert back to a signed value when needed.
• Operator precedence. &, |, ^ bind looser than == and +. Parenthesise: write (x >> k) & 1, not x >> k & 1 by reflex, and (a & b) == 0, not a & b == 0.
• Signed shifts and negatives. x & -x relies on two’s-complement; it works in Python, but reason carefully about negative inputs and sign bits.

Recap

Treat an integer as a bit-set and the operators as O(1) tools. Memorise the core tricks: x & 1 (parity), x & (x-1) (clear lowest set bit → count bits), x & -x (isolate lowest set bit), XOR cancels pairs (find the lone number), and the mask operations (1<<k to set/clear/toggle/test, (1<<n)-1 for a full mask, iterate a mask to enumerate subsets). Signal words: single number, count bits, subsets, power of two, without +. In Python, remember the 32-bit mask.

Practice: 10 solved problems on bit manipulation → — cover each one, solve it yourself, then check the tested code.

Next: Lesson 22 — Greedy Algorithms, making the locally-best choice.