Topic Lesson
Learn Bit Manipulation from scratch
A complete 4-step path: handwritten notebook primer, animated visualizer, speed check quiz, and compiler practice.
What is Bit Manipulation
notebook noteBit manipulation is the practice of working directly on the individual ones and zeros that form numbers in computer memory. Every integer is stored as a tiny row of electrical switches that are either on or off. Instead of running arithmetic loops, bitwise operations flip, mask, shift, or combine these switches in a single hardware cycle. This allows compact storage of sets and blazing-fast checks without allocating extra memory.
When to reach for it
Reach for bit manipulation when problems ask to find a unique non-duplicate number, count set bits, determine if a value is a power of two, or pack a set of small booleans into a single integer. Prompts mentioning constant O(1) auxiliary space constraints on array queries often hint at XOR cancellation. It is also the foundation of bitmask dynamic programming, where subsets of up to twenty items are tracked as integer masks.
How to think about it
Think of an integer as a fixed-length set of flags. Use bitwise AND to inspect if a specific bit is set, bitwise OR to turn a bit on, and bitwise XOR to flip a bit or cancel out matched pairs. Learn the standard bit tricks: n AND with n minus one clears the lowest set bit, which counts ones quickly, while n AND with negative n isolates the lowest set bit. When packing sets into masks, represent the empty set as zero and add item i by shifting one left by i and combining with OR.
Operation costs
measured big-O| Operation | Time |
|---|---|
| bitwise operation like AND, OR, or XOR | O(1) |
| count set bits across fixed integer width | O(1) |
| find single non-duplicate number using XOR | O(n) |
Common mistakes to avoid
- Forgetting that bitwise operators have lower operator precedence than equality and arithmetic comparisons in most languages, evaluating expressions in the wrong order without parentheses.
- Using signed right shift instead of unsigned logical right shift when processing negative numbers, which fills high-order bits with ones instead of zeros.
- Shifting bits by thirty-two or more on standard 32-bit integers, causing undefined behavior or wrapped bit shifts that yield incorrect masks.