5.2 Math & Bit Manipulation

Deep Dive: See the Bits

Beginner tip: Computers store numbers as bits (0s and 1s). Bit manipulation lets you do clever tricks: XOR finds the unique element in a list of pairs, AND checks if a bit is set, and shifting multiplies/divides by powers of 2. The key insight for interviews: XOR of a number with itself is 0, and XOR with 0 is itself. Pairs cancel out.

XOR -- Single Number Walkthrough

nums = [4, 1, 2, 1, 2]. Find the number that appears once.

Binary:
4 = 100
1 = 001
2 = 010
1 = 001
2 = 010

XOR all:  100 ^ 001 = 101
          101 ^ 010 = 111
          111 ^ 001 = 110
          110 ^ 010 = 100 = 4  <- ANSWER

Pairs cancel: 1^1=0, 2^2=0. Only 4 remains.

Sum Without + or - (Bit Manipulation)

Add 5 + 3 using only bits:

a=5 (101), b=3 (011)

Step 1: sum_without_carry = a ^ b = 110 (6)
        carry = (a & b) << 1 = (001) << 1 = 010 (2)

Step 2: a=110, b=010
        sum = 110 ^ 010 = 100 (4)
        carry = (110 & 010) << 1 = (010) << 1 = 100 (4)

Step 3: a=100, b=100
        sum = 100 ^ 100 = 000 (0)
        carry = (100 & 100) << 1 = 1000 (8)

Step 4: a=000, b=1000
        sum = 1000 (8)
        carry = 0 -> DONE. Answer: 8 = 5+3.

Brian Kernighan's -- Count Set Bits

n = 13 (1101):

n=1101, n-1=1100, n&(n-1)=1100. count=1  (removed rightmost 1)
n=1100, n-1=1011, n&(n-1)=1000. count=2
n=1000, n-1=0111, n&(n-1)=0000. count=3  DONE.

13 has 3 set bits.

---

Before You Start -- How to Think About Bits and Math

Bit Manipulation Essentials

The key XOR properties:
  a ^ a = 0       (anything XOR itself = 0)
  a ^ 0 = a       (anything XOR 0 = itself)
  XOR is commutative and associative

"Find the single number where all others appear twice"
  -> XOR all elements. Pairs cancel out. Single element remains.

Brian Kernighan's trick: n & (n-1) removes the lowest set bit.
  Use to count 1-bits: while n: n &= n-1; count += 1

Key Bit Operations

Operation	Code	What It Does
Check bit i	n & (1 << i)	Is bit i set?
Set bit i	n | (1 << i)	Turn on bit i
Clear bit i	n & ~(1 << i)	Turn off bit i
Toggle bit i	n ^ (1 << i)	Flip bit i
Lowest set bit	n & (-n)	Isolate rightmost 1
Remove lowest set bit	n & (n-1)	Clear rightmost 1

Math Patterns in Interviews

- "Without using + or -" -> Bit manipulation (carry = a & b, sum = a ^ b)
- "Power of 2" -> n & (n-1) == 0
- "GCD" -> Euclidean algorithm: gcd(a,b) = gcd(b, a%b)
- "Fast exponentiation" -> x^n: if n is even, (x^(n/2))^2. If odd, x * x^(n-1)

When You See These Problems, Think

1. "Find unique / single element" -> XOR
2. "Count bits" -> Brian Kernighan's
3. "Power of 2/3/4" -> Bit tricks or math
4. "Rotate matrix" -> Transpose + reverse (math on indices)
5. "Spiral matrix" -> Boundary tracking (pure index math)

Problems

#	Problem	Status
1	Single Number (XOR)	[ ]
2	Number of 1 Bits	[ ]
3	Counting Bits	[ ]
4	Missing Number	[ ]
5	Reverse Bits	[ ]
6	Sum of Two Integers	[ ]
7	Pow(x, n)	[ ]
8	Happy Number	[ ]
9	Rotate Image	[ ]
10	Spiral Matrix	[ ]

Notes