Overview
Bit manipulation operates directly on the binary representation of integers using &, |, ^, ~, <<, >>.
Analogy
A row of light switches (bits): AND turns off switches that differ, OR turns on any that are on, XOR toggles where they differ.
Step-by-step
- AND (&): both bits must be 1.
- OR (|): either bit must be 1.
- XOR (^): bits must differ; x^x=0, x^0=x.
- Shift: x<<1 multiplies by 2; x>>1 divides by 2.
- Check bit k: (x >> k) & 1. Set bit k: x | (1 << k). Clear bit k: x & ~(1 << k).
Visual
5=0101, 3=0011: 5&3=0001=1, 5|3=0111=7, 5^3=0110=6
Common mistakes
- Confusing & (bitwise) with and (logical).
- Negative number bit patterns differ between languages (Python has infinite precision, no fixed width).
Practice questions
- Check if a number is a power of 2: n > 0 and (n & n-1) == 0.
- Count set bits (popcount) using Brian Kernighan's algorithm.
Time
O(1) per operation, O(log n) for iteration over bits
AI Wisdom