Blind 75 — Binary / Bit Manipulation Pattern Guide

How to Identify a “Bit Manipulation” Problem

Interview Triggers

• “Without using +, -, * or /”
• “Count the number of 1 bits” / “set bits” / “hamming weight”
• “Find the missing / unique / duplicate number in O(1) space”
• “Reverse the bits”
• “Swap two numbers in place”
• Constraints mention 32-bit or unsigned integer

Which Sub-Pattern Does It Belong To?

If the prompt says…	Use this trick	Example LC
Add without arithmetic operators	XOR + AND-shift (carry)	371
Count set bits	n & (n-1) (Brian Kernighan)	191
Count bits for every number 0..n	DP: bits[i] = bits[i>>1] + (i&1)	338
Find the missing number in [0..n]	XOR all indices + values	268
Reverse 32-bit unsigned integer	Bit-by-bit shift loop	190

---

The Decision Tree

BIT MANIPULATION PROBLEM
│
├─ Arithmetic forbidden?
│   └─ XOR (sum without carry) + AND<<1 (carry) → LC 371
│
├─ Count something about bits?
│   ├─ Set bits in one number  → n & (n-1) trick → LC 191
│   └─ Set bits for range 0..n → DP using i>>1   → LC 338
│
├─ Find the odd-one-out / missing?
│   └─ XOR-all (pairs cancel)  → LC 268, LC 136
│
└─ Reverse / swap bits?
    └─ Shift loop, OR into result → LC 190

---

Key Bit Tricks (Cheat Sheet)

Trick	Effect	Example
n & 1	LSB (parity)	5 & 1 = 1
n >> 1	divide by 2	5 >> 1 = 2
n & (n-1)	clears lowest set bit	12 & 11 = 8
n & -n	isolates lowest set bit	12 & -12 = 4
a ^ a = 0	XOR pairs cancel	useful for “find unique”
a ^ 0 = a	XOR identity	start accumulator at 0
`n	(1 << k)`	set bit k
n & ~(1 << k)	clear bit k	turn OFF
n ^ (1 << k)	flip bit k	toggle

---

Bread & Butter Problems

#	Problem	LC #	Difficulty	Trick
1	Number of 1 Bits	191	Easy	n & (n-1)
2	Counting Bits	338	Easy	DP — bits[i] = bits[i>>1] + (i&1)
3	Missing Number	268	Easy	XOR-all
4	Reverse Bits	190	Easy	Shift loop

FAANG “Aha!” Problems

#	Problem	LC #	Difficulty	Trick
1	Sum of Two Integers	371	Medium	XOR + AND-shift carry

---

Java Implementation Tips

• Java int is always signed 32-bit. For unsigned semantics use >>> (logical shift right), NOT >> (arithmetic).
• Integer.bitCount(n) is a fast intrinsic — use it when allowed.
• Integer.numberOfTrailingZeros(n) / numberOfLeadingZeros(n) are intrinsics too.
• Loop while n != 0 (not n > 0) so negative numbers terminate.
• Long.parseLong(s, 2) / Integer.toBinaryString(n) are handy for debugging.

---

Senior Mental Trigger

“Pairs cancel → XOR. Lowest set bit → n & -n. Drop lowest set bit → n & (n-1).”