16 — Bit Manipulation

Neetcode Week 12c. Bit tricks are niche but pop up at Google often enough to be worth learning. The good news: there are only ~10 idioms, and once you've seen them, they're easy.

Binary basics
Operators
Common idioms (memorize these)
Pattern: XOR tricks
Pattern: Counting bits
Pattern: Bitmask DP
Pattern: Bitwise on signed integers
Walked-through problems
Pitfalls
Practice list

1. Binary basics

Decimal  Binary       Hex
0        0            0
1        1            1
2        10           2
5        101          5
10       1010         A
15       1111         F
255      11111111     FF

A 32-bit signed integer: leftmost bit is sign (0 = positive, 1 = negative two's-complement).

   sign     value bits
    │     ←  31 bits  →
   [s][b][b]....[b][b][b]
   bit 31              bit 0

Two's complement

To negate a number: flip all bits and add 1.

 5 = 0000 0101
-5 = 1111 1011    (flip and +1)

This is why ~x == -x - 1 in C / Java / Python (the formula matters for bit puzzles).

2. Operators

Op	Meaning	Example
`&`	AND	`0b1100 & 0b1010 = 0b1000`
`\|`	OR	`0b1100 \| 0b1010 = 0b1110`
`^`	XOR	`0b1100 ^ 0b1010 = 0b0110`
`~`	NOT	`~0 = -1` (in 2's complement)
`<<`	left shift	`1 << 3 = 8`
`>>`	right shift	`8 >> 1 = 4`

Truth tables

  a b   AND  OR  XOR
  0 0    0    0   0
  0 1    0    1   1
  1 0    0    1   1
  1 1    1    1   0

XOR is the odd-parity operator: 1 iff inputs differ.

3. Common idioms

Memorize these. Each is one line and unlocks many problems.

Idiom	Code	Meaning
Test bit `i`	`(x >> i) & 1`	0 or 1
Set bit `i`	`x \| (1 << i)`	turn on
Clear bit `i`	`x & ~(1 << i)`	turn off
Toggle bit `i`	`x ^ (1 << i)`	flip
Lowest set bit	`x & -x`	isolates lowest 1
Clear lowest set bit	`x & (x - 1)`	turns lowest 1 into 0
Test if power of 2	`x > 0 and (x & (x-1)) == 0`	0...010...0
Count set bits	`bin(x).count('1')` (Python) or Brian Kernighan loop	popcount
Round down to power of 2	`1 << (x.bit_length() - 1)`	floor
Round up to power of 2	`1 << x.bit_length()` if x != power-of-2, else x	ceil
Swap with XOR	`a^=b; b^=a; a^=b`	no temp variable

Brian Kernighan's bit count

def count_bits(x):
    cnt = 0
    while x:
        x &= x - 1                                       # clear lowest set bit
        cnt += 1
    return cnt

O(number of set bits), often faster than bit-by-bit scan for sparse numbers.

Swap without temp

a ^= b
b ^= a
a ^= b

(Cute, but slow vs a, b = b, a in Python — interview trivia only.)

4. Pattern: XOR tricks

XOR properties:

x ^ x = 0 — anything XORed with itself is 0.
x ^ 0 = x — XOR with 0 is identity.
XOR is commutative and associative.

These three facts power many "find the unique" problems.

Single Number (Easy)

Every number appears twice except one. Find it.

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

XOR of all → pairs cancel out, lone element remains. O(n) time, O(1) space.

Single Number II — appears 3 times

Every number appears 3 times except one (which appears once). Find it.

The XOR trick doesn't directly apply (3 isn't even). Generalize: count bits modulo 3.

def single_number_iii(nums):
    result = 0
    for i in range(32):
        bit_count = sum((x >> i) & 1 for x in nums)
        if bit_count % 3:
            result |= 1 << i
    # Handle negative numbers (Python ints are arbitrary precision)
    if result >= 2**31:
        result -= 2**32
    return result

Missing Number (Easy)

Array of n distinct numbers from 0..n. Find missing.

def missing_number(nums):
    res = len(nums)
    for i, x in enumerate(nums):
        res ^= i ^ x
    return res

XOR of 0..n xored with XOR of nums leaves only the missing number.

Two Numbers Appearing Once

Every number appears twice except two — find both.

def single_number_iv(nums):
    xor_all = 0
    for x in nums: xor_all ^= x          # = a ^ b (the two unique)
    diff_bit = xor_all & -xor_all         # lowest bit where a and b differ
    a = b = 0
    for x in nums:
        if x & diff_bit:
            a ^= x
        else:
            b ^= x
    return [a, b]

Split numbers by a bit where the two unique differ. Each group XORs to one of them.

5. Pattern: Counting bits

Number of 1 Bits (Easy)

def hamming_weight(n):
    cnt = 0
    while n:
        cnt += n & 1
        n >>= 1
    return cnt

Or n &= n - 1 trick (only counts set bits).

Counting Bits 0..n (Easy)

Return array [count_of_1s_in_i for i in 0..n].

def count_bits(n):
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        dp[i] = dp[i >> 1] + (i & 1)         # half + lowest bit
    return dp

dp[i] = dp[i // 2] + i % 2 — the number of bits is the count in i // 2 plus the lowest bit.

Reverse Bits (Easy)

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

Build the result by shifting left and OR-ing the bottom bit of input.

6. Pattern: Bitmask DP

When n ≤ ~20, you can encode "which subset is selected" in 2ⁿ states.

Travelling Salesman (n ≤ 20) — classic

dp[mask][i] = min cost to visit every city in mask, ending at i.

def tsp(dist, start=0):
    n = len(dist)
    INF = float('inf')
    dp = [[INF] * n for _ in range(1 << n)]
    dp[1 << start][start] = 0
    
    for mask in range(1 << n):
        for i in range(n):
            if not (mask >> i) & 1: continue
            if dp[mask][i] == INF: continue
            for j in range(n):
                if (mask >> j) & 1: continue              # j already in mask
                new_mask = mask | (1 << j)
                dp[new_mask][j] = min(dp[new_mask][j], dp[mask][i] + dist[i][j])
    
    return min(dp[(1 << n) - 1][i] + dist[i][start] for i in range(n))

Iterate all subsets of a set

n = 4
for mask in range(1 << n):                                # 2^n subsets
    subset = [i for i in range(n) if (mask >> i) & 1]
    print(subset)

Iterate all subsets of a subset

sub = mask
while sub > 0:
    # use sub
    sub = (sub - 1) & mask

Niche but powerful for partition DP.

7. Pattern: Bitwise on signed integers

In C++/Java, int is 32-bit. Right shift of negative numbers is implementation-defined for >>, defined for >>> (unsigned).

In Python, ints are arbitrary precision. To simulate 32-bit:

n &= 0xFFFFFFFF

Sum of Two Integers (without `+` or `-`)

Use bitwise.

def get_sum(a, b):
    MASK = 0xFFFFFFFF
    while b & MASK:
        carry = (a & b) << 1                  # carry bits
        a = a ^ b                             # sum without carry
        b = carry
    return a & MASK if a >= 0 else a

XOR = sum without carry; AND << 1 = carry. Loop until no carry. The MASK is needed in Python for negative numbers (otherwise the loop never terminates).

8. Walked-through problems

Subsets via bitmask

def subsets(nums):
    n = len(nums)
    res = []
    for mask in range(1 << n):
        subset = [nums[i] for i in range(n) if (mask >> i) & 1]
        res.append(subset)
    return res

Equivalent to backtracking but iterative. O(n · 2ⁿ).

Power of Two (Easy)

def is_power_of_two(n):
    return n > 0 and (n & (n - 1)) == 0

A power of 2 has exactly one bit set. n & (n-1) clears the lowest bit, leaving 0 only if there was just that one bit.

Counting Set Bits with DP

Already shown above (dp[i] = dp[i >> 1] + (i & 1)).

9. Pitfalls

Operator precedence

x & 1 == 1 is not (x & 1) == 1. In C/Python, == binds tighter than &. Always parenthesize:

((x >> i) & 1) == 1

Or just (x >> i) & 1 (truthy check).

Negative shifts

Right-shifting a negative int in C is implementation-defined for signed >>. Use >>> in Java, or convert to unsigned. In Python, >> of negatives works mathematically but might surprise:

-5 >> 1   # -3 (floor division)

Off-by-one in `1 << n`

1 << 32 in C/Java is undefined for 32-bit int. In Python it's fine (arbitrary precision). State your assumed bit width.

Counting all bits is slow

bin(x).count('1') is O(bits) — fine. for i in range(64): if (x >> i) & 1: ... is also O(64). Don't write nested loops over bits unnecessarily.

Confusing `^` with power

In Python ^ is XOR. ** is exponentiation. In math notation ^ is power, but not in code.

Forgetting Python ints are unbounded

x &= 0xFFFFFFFF to truncate to 32 bits when emulating fixed-width arithmetic.

10. Practice list

#	Problem	Pattern	Difficulty
136	Single Number	XOR	Easy
137	Single Number II	Bit-count mod 3	Medium
191	Number of 1 Bits	Popcount	Easy
338	Counting Bits	DP	Easy
190	Reverse Bits	Shift + OR	Easy
268	Missing Number	XOR or sum	Easy
7	Reverse Integer	Math/bit	Medium
371	Sum of Two Integers	Carry sim	Medium
78	Subsets	Bitmask iter	Medium
231	Power of Two	n & (n-1)	Easy

TL;DR ✅

XOR cancels pairs. Use it to find a unique element among duplicates.
x & (x - 1) clears lowest set bit. x & -x isolates it.
(n & (n-1)) == 0 tests power-of-two.
Bit DP: dp[i] = dp[i >> 1] + (i & 1) for popcount table.
Bitmask DP when n ≤ 20 — encode subsets in 2ⁿ states.
Always parenthesize &, |, ^ due to low precedence.
Python ints are arbitrary-precision — mask with 0xFFFFFFFF to simulate 32-bit.

Next: 17-patterns-cheatsheet.md.

External resources

NeetCode Bit Manipulation playlist: https://www.youtube.com/playlist?list=PLot-Xpze53lcCEd6dnP7HQGiNd5b_RMyG
Bit hacks reference: https://graphics.stanford.edu/~seander/bithacks.html
Sean Anderson's bit tricks: https://github.com/keon/bit-tricks