Bit manipulation can be confusing at first, but it's super useful. You see it in lots of coding problems, and it can make your code faster, lighter, and handle tricky cases like combinations or states.
With a few simple tricks, you can do things like check if a number is a power of two, find the only unique number in an array, or quickly generate all subsets.
Let's look at some patterns I've found interesting and see how they actually work in practice.
Quick Bit Refresher
Before we get into patterns, here's a short review of the basic bit operators
Bitwise Operators
-
AND (
&) - Keeps a bit set only if both are1. -
OR (
|) - Sets a bit if any one of them is1. -
XOR (
^) - Sets a bit if both are different. -
NOT (
~) - Flips all bits. -
Left Shift (
<<) - Moves bits to the left (like multiplying by 2). -
Right Shift (
>>) - Moves bits to the right (like dividing by 2).
Now it's all about spotting patterns and using them.
Common Bit Manipulation Patterns
These are some patterns that we see and are helpful to us
1. Check if a Number is a Power of Two
A number is a power of two if it has only one bit set.
For example, 1 (0001), 2 (0010), 4 (0100), 8 (1000), and so on.
The trick is simple:
n > 0 && (n & (n - 1)) == 0
How it works:
Subtracting 1 flips all bits after the rightmost set bit.
So, when you AND a number with n - 1, the result becomes zero only if there was just one bit set.
8 (1000)
7 (0111)
8 & 7 = 0000 -> Power of Two
When to use:
Useful when working with constraints like array sizes, segment trees, or memory blocks that must be powers of two.
Practice Problem:
2. Count Set Bits (Brian Kernighan's Algorithm)
Counting the number of 1s in a binary number can be done efficiently using this method.
The trick is simple:
int count = 0;
while (n>0) {
n &= (n - 1);
count++;
}
How it works:
Each time we do n & (n - 1), the rightmost set bit is removed.
We repeat this until the number becomes zero, counting how many bits were set.
13 (1101)
n = 1101 -> 1100 -> 1000 -> 0000
count = 3
When to use:
Useful in problems involving bit masks, subsets, or any situation where you need the number of set bits efficiently.
Practice Problems:
3. Extract Rightmost Set Bit
Sometimes you need to isolate the least significant 1 bit in a number.
The trick is simple:
int right = n & -n;
How it works:
-n is the two's complement of n.
When you AND n with -n, all bits except the rightmost set bit become 0.
12 (1100)
-12 (0100 in effect for AND)
12 & -12 = 0100 -> 4
When to use:
Useful in submask iteration, Fenwick tree updates, and bit-based indexing.
Practice Problem:
4. Swap Two Numbers Without Temp
You can swap two numbers without using an extra variable using XOR.
The trick is simple:
a = a^b;
b = a^b;
a = a^b;
How it works:
XOR has a property that allows you to combine and separate values.
After these three steps, the values of a and b are swapped.
Example:
a = 5 (0101)
b = 7 (0111)
Step 1: a ^= b -> a = 0101 ^ 0111 = 0010
Step 2: b ^= a -> b = 0111 ^ 0010 = 0101
Step 3: a ^= b -> a = 0010 ^ 0101 = 0111
When to use:
Useful in memory-constrained environments or when extra variables are not allowed.
Practice Problem:
do you actually need it 🤨
5. XOR Prefix Sum (Cumulative XOR)
XOR prefix sums help calculate the XOR of any subarray quickly.
The trick is simple:
prefix[i] = prefix[i - 1] ^ arr[i];
xor(l, r) = prefix[r] ^ prefix[l - 1];
How it works:
The XOR of a subarray from index l to r can be found by XORing the prefix up to r with the prefix up to l - 1.
This works because XOR is its own inverse.
Example:
arr = [1, 2, 3, 4]
prefix = [0, 1, 3, 0, 4] // prefix[0] = 0
XOR(1, 3) = prefix[3] ^ prefix[0] = 0 ^ 0 = 0
When to use:
Useful in problems involving range XOR queries, parity checks, or XOR-based subarray problems.
Practice Problems:
6. Power of Four Check
A number is a power of four if it has only one bit set and that bit is in an even position (0-based index from the right).
The trick is simple:
public boolean isPowerOfFour(int n) {
return n > 0
&& (n & (n - 1)) == 0
&& (n % 3 == 1);
}
How it works:
n > 0 ensures the number is positive.
(n & (n - 1)) == 0 checks that the number has only one bit set.
n % 3 == 1 ensures that the set bit is at an even position. All powers of four (1, 4, 16, 64…) leave a remainder of 1 when divided by 3, which automatically eliminates numbers that are powers of two but not powers of four (like 2, 8, 32…).
Example:
16 -> binary 10000 (set bit at position 4, even)
16 > 0 True
16 & (16 - 1) = 16 & 15 = 0 True
16 % 3 = 1 -> Power of Four
8 -> binary 1000 (set bit at position 3, odd)
8 > 0 True
8 & (8 - 1) = 8 & 7 = 0 True
8 % 3 = 2 -> Not Power of Four
Practice Problem:
7. XOR from 1 to n Pattern
XOR of all numbers from 1 to n follows a repeating pattern every 4 numbers.
The trick is simple:
n % 4 == 0 -> result = n
n % 4 == 1 -> result = 1
n % 4 == 2 -> result = n + 1
n % 4 == 3 -> result = 0
How it works:
The XOR sequence repeats every 4 numbers, which allows you to find the XOR of 1 to n in O(1) time.
XOR has two key properties:
-
x ^ x = 0 -
x ^ 0 = x
If you look at the sequence of XOR from 1:
1 -> 1
1 ^ 2 -> 3
1 ^ 2 ^ 3 -> 0
1 ^ 2 ^ 3 ^ 4 -> 4
1 ^ 2 ^ 3 ^ 4 ^ 5 -> 1
1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 -> 7
1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 -> 0
1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 ^ 8 -> 8
You can see the results repeat every 4 numbers: [n, 1, n+1, 0].
This happens because each group of 4 numbers cancels out in a specific way due to XOR properties.
Example:
XOR(1..5) -> 1^2^3^4^5
5 % 4 = 1 -> result = 1
When to use:
Useful in problems with range XOR queries, finding missing numbers, or single number problems.
Practice Problems:
8. Subset Generation via Bitmask
You can generate all subsets of a set using bitmasks. Each element is either included or not included in a subset.
The trick is simple:
for (int mask = 0; mask < (1 << n); mask++) {
for (int i = 0; i < n; i++) {
if ((mask & (1 << i)) != 0) {
// include element i in the subset
}
}
}
How it works:
Each number from 0 to 2^n - 1 represents a subset.
Each bit in the number decides whether to include the corresponding element in the subset.
Rightmost bit -> arr[0], next bit -> arr[1], and so on.
Example:
arr = [a, b, c]
mask = 5 -> binary 101
Check bits:
i = 0 -> 1 -> include a
i = 1 -> 0 -> exclude b
i = 2 -> 1 -> include c
Subset = {a, c}
Practice Problems:
9. Gray Code Conversion
Gray code is a binary sequence where two consecutive numbers differ by only one bit.
It is often used in hardware design or algorithms where minimal bit changes are required.
The trick is simple:
int gray = n ^ (n >> 1);
int binary = 0;
for (int g = gray; g != 0; g >>= 1) {
binary ^= g;
}
How it works:
- Binary to Gray:
Shift the number n one bit to the right.
XOR the original number with the shifted number.
This ensures that only one bit changes between consecutive numbers.
- Gray to Binary:
Start with binary = 0.
Take the Gray code and repeatedly XOR it with itself shifted right.
This reconstructs the original binary number by accumulating changes from left to right.
Example:
Binary 5 -> 101
Shift right -> 010
XOR -> 101 ^ 010 = 111 -> Gray code
Gray 111 -> Binary:
Start binary = 0
Step 1: binary ^= 111 -> 111
Step 2: shift 111 >> 1 = 011, binary ^= 011 -> 100
Step 3: shift 011 >> 1 = 001, binary ^= 001 -> 101
Binary = 101 (original number)
When to use:
Useful in circular sequences where only one bit should change at a time.
Helpful in hardware counters, encoders, and minimizing errors during state changes.
Practice Problem:
10. Highest Set Bit (Most Significant Bit)
Finding the position of the highest set bit tells us the largest power of two less than or equal to a number.
The trick is simple:
int msb(int n) {
int pos = 0;
while (n > 0) {
n >>= 1;
pos++;
}
return pos - 1;
}
How it works:
Keep shifting the number right until it becomes zero.
Count how many shifts it takes. the last set bit before zero is the highest bit.
Example:
n = 10 -> binary 1010
Shift 1: 101 -> pos 1
Shift 2: 10 -> pos 2
Shift 3: 1 -> pos 3
Shift 4: 0 -> stop
Highest set bit position = 3 (value 8)
When to use:
Useful in bucket indexing, determining ranges of powers of two, or binary segmentation problems.
Practice Problems:
These are some patterns I found interesting and wanted to share from what I learned.
Top comments (0)