13.1 Bit Manipulation

1. What Is Bit Manipulation?

Inside hardware, every integer is stored in binary (powers of 2: ..., 8, 4, 2, 1). For example, the number 12 (8 + 4) is stored as 1100. Bit Manipulation uses CPU-level bitwise operators (&, |, ^, ~, <<, >>) to inspect or flip those 0s and 1s directly in O(1) time and O(1) memory:

• AND (&): 1 only if both bits are 1.
• OR (|): 1 if either bit is 1.
• XOR (^): 1 if the two bits are different, 0 if they are the same.
• Left / Right Shift (<<, >>): 1 << i puts a 1 at bit position i (2^i); (n >> i) & 1 reads bit i.

Truth Table & Essential Bitmask Cheat Sheet

• Check if n is a Power of Two (1, 2, 4, 8, 16...): Powers of two have exactly one 1-bit in binary (8 = 1000). So n > 0 and (n & (n - 1)) == 0 is True if and only if n is a power of two!
• Isolate the Lowest Set 1-Bit (n & -n): In two's complement binary, -n is ~n + 1, so n & -n keeps only the rightmost 1-bit (used in Fenwick / Binary Indexed Trees).

2. Why Do We Need Bit Manipulation & How Do the Two Core Tricks Work?

Trick 1: XOR Pair Cancellation (x ^ x = 0 and x ^ 0 = x)

Suppose an array has 99,999 numbers where every number appears twice except one unique number (Single Number), or a range 0..N is missing one number (Missing Number).

• A Hash Set finds the answer in O(N) time, but uses O(N) extra memory.
• Because x ^ x = 0, XORing all numbers together cancels every duplicate pair into 0, leaving only the unique number in O(N) time and O(1) memory!

Trick 2: Clearing the Lowest Set 1-Bit (n & (n - 1))

Look at what happens in binary when you subtract 1 from n = 12 (1100):

• n = 1100
• n - 1 = 1011
• n & (n - 1) = 1000 (the rightmost 1-bit vanished in one step!).

This gives us two famous interview solutions:

1. Count 1-bits (Number of 1 Bits): Loop n = n & (n - 1) until n == 0.
2. Dynamic Programming on Bits (Counting Bits): For every number i from 1..N, i has the exact same 1-bits as i & (i - 1), plus one more 1-bit: dp[i] = dp[i & (i - 1)] + 1!

3. Basic Operations & Walkthroughs (All 4 Languages)

# 1. Basic Bit Operations on n = 12 (binary 1100)
n = 12
bit_2 = (n >> 2) & 1           # Read bit 2 -> 1
set_bit_0 = n | (1 << 0)       # Turn ON bit 0 -> 13 (1101)
clear_bit_2 = n & ~(1 << 2)    # Turn OFF bit 2 -> 8 (1000)

# 2. XOR Cancellation: Find unique number in O(N) time, O(1) space
def single_number(nums: list[int]) -> int:
  ans = 0
  for x in nums:
      ans ^= x
  return ans

# 3. Clear Lowest Set Bit: Count 1-bits in O(popcount)
def hamming_weight(n: int) -> int:
  bits = 0
  while n:
      n &= n - 1
      bits += 1
  return bits

4. Core Interview Patterns & Common Traps

# 1. Missing Number in [0..n] via Index-Value XOR:
ans = len(nums)
for i, x in enumerate(nums):
  ans ^= i ^ x

# 2. Counting Bits for 0..n in O(N) time:
dp = [0] * (n + 1)
for i in range(1, n + 1):
  dp[i] = dp[i & (i - 1)] + 1

5. Practice On Your Own (Curated Submodule Problems)