Bit Manipulation

Back to Index

Use when: XOR tricks, subset generation, power of 2 checks, counting bits, single number problems.

Common Tricks

# Check if bit i is set
(n >> i) & 1
 
# 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
 
# XOR: a ^ a = 0, a ^ 0 = a
# Use to find the single non-duplicate in a list
result = 0
for num in nums:
    result ^= num  # all pairs cancel, single number remains
 
# Count set bits (Brian Kernighan)
count = 0
while n:
    n &= n - 1  # clears lowest set bit
    count += 1

XOR Properties

• a ^ a = 0
• a ^ 0 = a
• Commutative and associative
• XOR of a range [1..n] follows a pattern based on n % 4

---

Problems Using This Pattern