Bit Manipulation

Fast integer operations using binary representation. Small topic, high payoff — problems are easy once you know the tricks.

---

Bit Operators

a & b   # AND  — both bits 1
a | b   # OR   — either bit 1
a ^ b   # XOR  — bits differ
~a      # NOT  — flip all bits (~a = -a - 1 in Python)
a << n  # left shift  — multiply by 2^n
a >> n  # right shift — divide by 2^n (floor)

---

Essential Tricks

# Check if bit i is set
(n >> i) & 1  # 1 if set, 0 if not

# Set bit i
n | (1 << i)

# Clear bit i
n & ~(1 << i)

# Toggle bit i
n ^ (1 << i)

# Check power of 2
n > 0 and (n & (n - 1)) == 0
# n = 4 = 100, n-1 = 011, 100 & 011 = 0 ✓
# n = 6 = 110, n-1 = 101, 110 & 101 = 100 ≠ 0 ✗

# Turn off rightmost set bit
n & (n - 1)

# Isolate rightmost set bit
n & (-n)   # or: n & (~n + 1)

# Count set bits (Brian Kernighan)
count = 0
while n:
    n &= n - 1   # removes rightmost set bit
    count += 1

# Python built-in
bin(n).count('1')  # or
n.bit_count()      # Python 3.10+

---

XOR Properties

a ^ a = 0       # same value cancels
a ^ 0 = a       # zero identity
a ^ b ^ a = b   # cancel pair
XOR is commutative and associative

---

Problem Patterns

Single Number (XOR cancel pairs)

def singleNumber(nums: list[int]) -> int:
    result = 0
    for n in nums:
        result ^= n
    return result
# [2,2,1] → 2^2^1 = 0^1 = 1

Single Number III (two non-duplicate)

def singleNumber(nums: list[int]) -> list[int]:
    xor = 0
    for n in nums:
        xor ^= n          # xor = a ^ b (the two singles)

    # find any set bit that differs between a and b
    diff_bit = xor & (-xor)   # rightmost set bit

    a = 0
    for n in nums:
        if n & diff_bit:  # partition: numbers with this bit set
            a ^= n        # one of a,b is here, pairs cancel
    return [a, xor ^ a]

Sum of Two Integers (no + operator)

def getSum(a: int, b: int) -> int:
    mask = 0xFFFFFFFF   # 32-bit mask
    while b & mask:
        carry = (a & b) << 1
        a = a ^ b
        b = carry
    return a if b == 0 else a & mask  # handle negative (Python's int is unbounded)

Counting Bits (DP + bit trick)

def countBits(n: int) -> list[int]:
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        dp[i] = dp[i >> 1] + (i & 1)   # dp[i/2] + last bit
    return dp

Reverse Bits

def reverseBits(n: int) -> int:
    result = 0
    for _ in range(32):
        result = (result << 1) | (n & 1)
        n >>= 1
    return result

Find Missing Number

def missingNumber(nums: list[int]) -> int:
    result = len(nums)
    for i, n in enumerate(nums):
        result ^= i ^ n   # XOR index and value — pairs cancel, missing stays
    return result

---

Common Problems Table

---

Bitmask for Subsets

# Enumerate all subsets of [0..n-1] using bitmask
n = 3
for mask in range(1 << n):   # 0 to 2^n - 1
    subset = [i for i in range(n) if mask & (1 << i)]
    print(subset)
# [], [0], [1], [0,1], [2], [0,2], [1,2], [0,1,2]

Useful for: subsets problems, visited states in graph DP, combination enumeration.

---

Python Gotchas

# Python integers are unbounded — no 32-bit overflow
# Mask to 32-bit: & 0xFFFFFFFF
# Convert masked int to signed: if result > 0x7FFFFFFF: result -= 0x100000000

# ~ operator: ~n = -(n+1) in Python
~5 = -6  # not 0b...11111010 as you'd expect from C

---

Related

• [[DSA/Data Structures/Hash Map]] — alternative O(n) for single number
• [[DSA/DSA Techniques for Interviews/12. Dynamic Programming]] — counting bits uses DP
• [[DSA/DSA Topics]] — DSA index