Bit Manipulation
Last Updated: December 9, 2025
Most developers avoid bit manipulation because it looks intimidating. Shifting bits, flipping 1s and 0s, reading cryptic expressions like n & (n - 1). It feels like black magic.
But here is the truth: bit manipulation is one of the highest ROI topics for coding interviews. A handful of techniques can solve dozens of problems, often in O(1) space and with blazing fast performance.
Computers think in bits. When you learn to think in bits too, you unlock solutions that would otherwise seem impossible.
In this chapter, we will cover:
- What is bit manipulation and why it matters
- The 6 bitwise operators you need to know
- Essential bit manipulation techniques
- Common patterns with sample problems
- LeetCode problems to practice
What is Bit Manipulation?
Bit manipulation is the process of performing operations directly on the binary representation of numbers. Instead of working with decimal values, you work with individual bits (0s and 1s).
Every integer in a computer is stored as a sequence of bits. For example, the number 5 is stored as 101 in binary (assuming 3 bits for simplicity).
Why Learn Bit Manipulation?
- Speed: Bitwise operations are among the fastest operations a CPU can perform. They happen in a single clock cycle.
- Space Efficiency: You can store multiple boolean flags in a single integer. Instead of using an array of booleans, one 32-bit integer can hold 32 flags.
- Interview Favorite: Companies like Google, Amazon, and Meta love bit manipulation problems because they test fundamental computer science knowledge.
- Elegant Solutions: Many problems that seem to require O(n) space can be solved in O(1) space using bit tricks.
The 6 Bitwise Operators
Before diving into techniques, you need to understand the six fundamental bitwise operators.
1. AND (&)
Returns 1 only if both bits are 1.
Use case: Check if a specific bit is set, clear bits, extract bits.
2. OR (|)
Returns 1 if at least one bit is 1.
Use case: Set specific bits to 1.
3. XOR (^)
Returns 1 if the bits are different.
Use case: Toggle bits, find unique elements, swap values.
Key property: a ^ a = 0 and a ^ 0 = a
4. NOT (~)
Flips all bits (0 becomes 1, 1 becomes 0).
Note: In most languages, ~n = -(n + 1) due to two's complement representation.
5. Left Shift (<<)
Shifts bits to the left by specified positions. Each shift multiplies by 2.
Formula: n << k = n × 2^k
6. Right Shift (>>)
Shifts bits to the right by specified positions. Each shift divides by 2 (integer division).
Formula: n >> k = n / 2^k (integer division)
Essential Bit Manipulation Techniques
Now let's look at the techniques that appear repeatedly in coding interviews.
1. Check if a Bit is Set
To check if the k-th bit (0-indexed from right) is set to 1:
How it works:
1 << kcreates a number with only the k-th bit setn & (1 << k)isolates that bit- If the result is non-zero, the bit was set
2. Set a Bit
To set the k-th bit to 1:
How it works: OR with a mask that has 1 at position k.
3. Clear a Bit
To clear (unset) the k-th bit:
How it works: AND with a mask that has 0 at position k and 1s everywhere else.
4. Toggle a Bit
To flip a bit (0 to 1, or 1 to 0):
How it works: XOR with a mask that has 1 at position k.
5. Check if Power of 2
A number is a power of 2 if it has exactly one bit set.
How it works:
- Powers of 2 have only one bit set: 1, 10, 100, 1000...
- Subtracting 1 flips all bits after (and including) the rightmost set bit
- AND of these gives 0 only for powers of 2
6. Count Set Bits (Brian Kernighan's Algorithm)
Count the number of 1s in the binary representation:
Why it works: n & (n - 1) clears the rightmost set bit. We count how many times we can do this before n becomes 0.
Time complexity: O(number of set bits), not O(32)
7. Get the Rightmost Set Bit
Extract the rightmost bit that is set to 1:
How it works: In two's complement, -n = ~n + 1. This creates a number where only the rightmost set bit survives the AND.
8. Turn Off the Rightmost Set Bit
This is the same trick used in counting set bits and checking power of 2.