Pattern — Bit Tricks

Cheat sheet

Trick	Code	Use case
Check bit i	(x >> i) & 1	Test
Set bit i	x | (1 << i)	Mark
Clear bit i	x & ~(1 << i)	Unmark
Toggle bit i	x ^ (1 << i)	Flip
Lowest set bit	x & -x	Isolate LSB
Clear lowest set bit	x & (x-1)	Count bits
Power of 2?	x > 0 && (x & (x-1)) === 0	LC #231
Number of bits	`(x.toString(2).match(/1/g)
All bits XOR	a ^ b ^ b = a	Single number
Swap without temp	a^=b; b^=a; a^=b	Trick
Power of 4?	x > 0 && (x & (x-1)) === 0 && (x & 0x55555555) !== 0	LC #342

JS pitfalls (cực quan trọng)

>>> vs >> trong JavaScript

• >> là arithmetic shift — giữ dấu (cho số âm thành rất lớn).
• >>> là logical shift — chèn 0 từ trái.
• Khi đếm bits của uint32 (vd LC #190 reverse bits, #191 count bits), PHẢI dùng >>>.

// SAI:
function countBits(n: number): number {
  let count = 0;
  while (n) { count += n & 1; n >>= 1; }   // n âm → vô hạn loop!
  return count;
}
 
// ĐÚNG:
function countBits(n: number): number {
  let count = 0;
  while (n) { count += n & 1; n >>>= 1; }  // logical shift
  return count;
}

Top problems

Bài	LC	Trick
Single Number	LC #136	XOR all
Single Number II	LC #137	State machine 3 mod
Single Number III	LC #260	XOR + lowest set bit để partition
Number of 1 Bits	LC #191	Brian Kernighan x & (x-1)
Counting Bits	LC #338	DP dp[i] = dp[i>>1] + (i&1)
Power of Two	LC #231	x & (x-1) === 0
Missing Number	LC #268	XOR [0..n] ^ nums
Reverse Bits	LC #190	Loop 32 lần với >>>
Sum of Two Integers	LC #371	a^b + (a&b)<<1 (carry)
Maximum XOR	LC #421	Trie of bits
Bitwise AND of Range	LC #201	Common prefix

Bitmask DP

Khi state có $\le 20$ phần tử, lưu state vào 1 bitmask $\mathrm{0..}{2}^N-1$. Vd:

• TSP / Hamiltonian (LC #847, #943)
• Partition into K Equal Subsets (LC #698)
• Minimum Cost to Connect Points (subset DP)

→ Nguồn: 02-Bit-Manipulation, 10-Advanced-DP (Bitmask DP section)