Bit Manipulation

1 / 8

Why bits?

  • Constant-time operations
  • One-bit-at-a-time reasoning
  • Shows up everywhere
2 / 8

Operators

  • AND, OR, XOR
  • Shifts as powers of two
  • XOR cancels duplicates
3 / 8

Classic tricks

  • n & (n-1) clears lowest set bit
  • n & -n isolates lowest set bit
  • Count bits by repeated clearing
4 / 8

Range AND

  • AND keeps common prefix
  • Shift until left == right
5 / 8

Per-bit constraints

  • Decide flips per bit for OR
  • Each bit is independent
6 / 8

Max XOR

  • Build from highest bit down
  • Prefix set or trie
7 / 8

Build

  • Single number
  • Power of two
  • Hamming weight
  • Range AND
  • Min flips for OR
  • Max XOR pair
8 / 8
←/→ or click edges to navigate · ? help · N notes · F fullscreen