Bit Manipulation problems, grouped by pattern
Bit tricks turn some problems into one line. XOR cancels pairs, n & (n - 1) clears the lowest set bit, and shifting checks any single bit. Worth knowing for the missing and repeated number family.
When to reach for it
- Every element appears twice except one
- Check, set or count bits
- Constant extra space is required
Mistakes to watch for
- Sign issues with >> vs >>> in Java
- Operator precedence of & vs ==
- Assuming 32-bit ints hold every value
The 12 problems
1Basics
- Decimal to binary Animated Easy
- Convert Binary Number in a Linked List to Integer Animated Easy
- K-th Bit is Set or Not Animated Easy
- Odd or Even Animated Easy
2Tricks to remember
- Number of 1 Bits Animated Easy
- Set the rightmost unset bit Animated Easy
- XOR of 1 to n Numbers Animated Easy
3XOR Basics
- Swap two numbers Animated Easy
- Hamming Distance Animated Easy
4Missing / Repeated Numbers
- Single Number Animated Easy
- Missing Number Animated Easy
- Two numbers with odd occurrences Animated Medium