Bit Manipulation: Complete Guide with XOR and Bit Tricks
Bit manipulation is one of those topics that looks like magic on a whiteboard until you learn the small set of operations that cover almost every interview problem. XOR cancels duplicates. n & (n-1) clears the lowest set bit. A mask with a shift reads or writes a single bit.
Definition: bit manipulation means reading, setting, clearing, or toggling individual bits within an integer using operators like AND (&), OR (|), XOR (^), NOT (~), and shifts («, »). Instead of treating a number as a single value, you treat it as a compact array of boolean flags.
This is what makes bit manipulation so powerful. An operation that would require a loop, a hash set, or a conditional branch can often be replaced with a single instruction. Every interview problem in this category is about recognizing when that substitution is possible.
Real-World Analogy
Think of an integer as a row of 32 light switches. Each switch is either on (1) or off (0). Most programming treats the whole row as a single brightness reading. Bit manipulation means reading and writing individual switches.
AND checks two rows and leaves a switch on only if both rows have it on. OR leaves a switch on if either row has it on. XOR turns a switch on only when the two rows disagree. A left shift slides the whole row one position to the left and adds a zero at the new spot on the right.
The skill is learning to see which switch operation maps to the problem you are solving. Finding the unique element in a sea of duplicates? That is XOR. Checking whether a number is a power of two? That is n > 0 combined with n & (n-1).
Visual Explanation
The following diagram shows how each bitwise operation transforms two 4-bit inputs.
graph TD
subgraph Input
A["A: 1010 (10)"]
B["B: 1100 (12)"]
end
subgraph Operations
AND["AND (&): 1000"]
OR["OR (|): 1110"]
XOR["XOR (^): 0110"]
end
A --> AND
B --> AND
A --> OR
B --> OR
A --> XOR
B --> XOR
AND keeps only the bits that are set in both numbers. OR keeps bits set in either. XOR keeps bits that differ. These three operations, combined with shifts, are the entire vocabulary of bit manipulation.
When to Use This Pattern
The pattern is the right tool when these conditions show up.
- A problem asks about duplicates, missing numbers, or unique elements in an array where other values appear in pairs. XOR cancellation handles this in a single pass with no extra memory.
- You need to check, set, or count specific bits. Operations like
(n >> k) & 1for reading orn | (1 << k)for writing are constant-time and make the intent exact. - The problem involves powers of two, either checking for them or decomposing a number into powers of two. The trick
n & (n - 1)is the key. - You need a compact set of flags or states, especially when the universe of possible values is small and bounded. An integer can replace a boolean array, saving memory and lookup time.
- The problem explicitly restricts you from using arithmetic operators or asks you to implement them. Bitwise operators are the only path forward.
Complexity Analysis
| Operation | Time | Space | Notes |
|---|---|---|---|
| Read or write a single bit | O(1) | O(1) | A single CPU instruction |
| XOR cancellation | O(N) | O(1) | One pass, one accumulator |
| Count set bits (Kernighan’s) | O(k) | O(1) | k equals number of set bits |
| Power of two check | O(1) | O(1) | Single AND of n and n-1 |
| Generate all subsets | O(2^N) | O(1) | Per iteration; output adds O(2^N) |
The time for most operations is
Common Mistakes
Forgetting parentheses around bitwise operations. (x & 1) == 0 is correct. x & 1 == 0 evaluates as x & (1 == 0), which becomes x & 0 and always produces 0. Always wrap bitwise expressions in parentheses when combining them with comparison operators. To catch this during practice, add parentheses around every bitwise expression before writing the comparison instead of relying on precedence tables.
Using the wrong shift direction for extraction. To read the bit at position k, you right-shift by k and mask with 1: (n >> k) & 1. Beginners sometimes write (n << k) & 1, which shifts the wrong way. Trace a concrete example: if n = 8 (binary 1000), extracting bit 3 should give 1. (8 >> 3) & 1 equals 1. (8 << 3) & 1 equals 0.
Assuming right shift of a negative number fills with zeros. In languages with signed integers, >> on a negative number performs sign extension. The leftmost bits fill with 1 instead of 0, which can create an infinite loop if you are counting bits by right-shifting until the number reaches 0. Use >>> (unsigned right shift) where available, or mask with a fixed bit count. To catch this, always check whether your input can be negative and handle the shift accordingly.
Off-by-one in bit positions. Bit positions are 0-indexed from the least significant bit. Position 0 is the 1s place, position 1 is the 2s place, position k is the 2^k place. Beginners sometimes treat position 1 as the 1s place. Verify your understanding by tracing: setBit(0, 0) should return 1, and setBit(0, 1) should return 2.
Related Patterns
- Math Algorithms . Bit manipulation is the implementation layer for many arithmetic tricks like checking divisibility by powers of two or computing absolute values without branching.
- Hash Table . Bitmasking offers a space-efficient alternative to a hash set when the key space is small and bounded. A single integer can replace a boolean array of size 32 or 64.
- Dynamic Programming . DP over subsets uses bitmasks to represent state, combining recursion with bit-level tracking for problems like the traveling salesman.
Next Steps
Once the concepts are clear, the next step is making the operations automatic. Check out the code templates for memorizable implementations, then work through the practice problems to apply bit manipulation to real interview questions.