Bit manipulation means working directly with the binary representation of numbers using bitwise operators. Computers already think in bits — so these operations are blazing fast (single CPU instruction).
In simple language, instead of doing math the “normal” way, we flip individual 0s and 1s inside a number. It feels like a magic trick, but it’s just math at the lowest level.
The Bitwise Operators
Here’s the toolkit. Everything operates on individual bits:
| Operator | Symbol | What it does |
|---|---|---|
| AND | & | Both bits must be 1 to get 1 |
| OR | | | Either bit being 1 gives 1 |
| XOR | ^ | Bits must be different to get 1 |
| NOT | ~ | Flips all bits |
| Left Shift | << | Shifts bits left (multiply by 2) |
| Right Shift | >> | Shifts bits right (divide by 2) |
Why It Matters in Interviews
Bit manipulation shows up in interviews because:
- It leads to O(1) space solutions where other approaches need extra memory
- Some problems are literally impossible to solve optimally without XOR tricks
- It tests whether we understand how numbers work under the hood
Common Tricks
Check Even or Odd
The last bit of any number tells us if it’s even (0) or odd (1). Way faster than using modulo.
function isOdd(n) {
return (n & 1) === 1; // last bit is 1 = odd
}
// 5 in binary: 101 -> last bit is 1 -> odd
// 4 in binary: 100 -> last bit is 0 -> evendef is_odd(n):
return (n & 1) == 1 # last bit is 1 = odd
# 5 in binary: 101 -> last bit is 1 -> odd
# 4 in binary: 100 -> last bit is 0 -> evenstatic boolean isOdd(int n) {
return (n & 1) == 1; // last bit is 1 = odd
}
// 5 in binary: 101 -> last bit is 1 -> odd
// 4 in binary: 100 -> last bit is 0 -> evenSwap Two Numbers Without a Temp Variable
XOR has a cool property: a ^ a = 0 and a ^ 0 = a. We can use this to swap.
function swap(a, b) {
a = a ^ b; // a now holds combined info
b = a ^ b; // b gets original a
a = a ^ b; // a gets original b
return [a, b];
}
// swap(3, 7) => [7, 3]def swap(a, b):
a = a ^ b # a now holds combined info
b = a ^ b # b gets original a
a = a ^ b # a gets original b
return a, b
# swap(3, 7) => (7, 3)static void swap(int a, int b) {
a = a ^ b; // a now holds combined info
b = a ^ b; // b gets original a
a = a ^ b; // a gets original b
System.out.println(a + ", " + b);
}
// swap(3, 7) => prints "7, 3"Check if a Number is a Power of 2
Powers of 2 in binary have exactly one 1-bit: 1, 10, 100, 1000… The trick: n & (n - 1) removes the lowest set bit. If the result is 0, there was only one bit set.
function isPowerOfTwo(n) {
return n > 0 && (n & (n - 1)) === 0;
}
// 8 = 1000, 7 = 0111 -> 1000 & 0111 = 0000 -> true
// 6 = 0110, 5 = 0101 -> 0110 & 0101 = 0100 -> falsedef is_power_of_two(n):
return n > 0 and (n & (n - 1)) == 0
# 8 = 1000, 7 = 0111 -> 1000 & 0111 = 0000 -> True
# 6 = 0110, 5 = 0101 -> 0110 & 0101 = 0100 -> Falsestatic boolean isPowerOfTwo(int n) {
return n > 0 && (n & (n - 1)) == 0;
}
// 8 = 1000, 7 = 0111 -> 1000 & 0111 = 0000 -> true
// 6 = 0110, 5 = 0101 -> 0110 & 0101 = 0100 -> falseCount Set Bits (Hamming Weight)
We keep clearing the lowest set bit until the number becomes 0. Each iteration removes exactly one 1-bit.
function countBits(n) {
let count = 0;
while (n > 0) {
n = n & (n - 1); // remove lowest set bit
count++;
}
return count;
}
// countBits(13) => 3 (13 = 1101, three 1-bits)def count_bits(n):
count = 0
while n > 0:
n = n & (n - 1) # remove lowest set bit
count += 1
return count
# count_bits(13) => 3 (13 = 1101, three 1-bits)static int countBits(int n) {
int count = 0;
while (n > 0) {
n = n & (n - 1); // remove lowest set bit
count++;
}
return count;
}
// countBits(13) => 3 (13 = 1101, three 1-bits)Time: O(k) where k is the number of set bits. That’s even better than O(log n).
XOR Patterns
XOR is the star of bit manipulation interviews. Key properties to remember:
a ^ a = 0(anything XOR itself is 0)a ^ 0 = a(anything XOR zero is itself)- XOR is commutative and associative (order doesn’t matter)
Find the Single Number
Given an array where every element appears twice except one, find the unique element. XOR everything together — the pairs cancel out and we’re left with the answer.
function singleNumber(nums) {
let result = 0;
for (const num of nums) {
result ^= num; // pairs cancel: a ^ a = 0
}
return result;
}
// singleNumber([4, 1, 2, 1, 2]) => 4
// 4^1^2^1^2 = 4^(1^1)^(2^2) = 4^0^0 = 4def single_number(nums):
result = 0
for num in nums:
result ^= num # pairs cancel: a ^ a = 0
return result
# single_number([4, 1, 2, 1, 2]) => 4
# 4^1^2^1^2 = 4^(1^1)^(2^2) = 4^0^0 = 4static int singleNumber(int[] nums) {
int result = 0;
for (int num : nums) {
result ^= num; // pairs cancel: a ^ a = 0
}
return result;
}
// singleNumber([4, 1, 2, 1, 2]) => 4Time: O(n), Space: O(1). No hash maps needed. That’s the beauty of XOR.
Find Two Non-Repeating Numbers
Given an array where every element appears twice except two, find both unique elements. This is a trickier extension.
The idea: XOR everything to get a ^ b. Since a and b are different, at least one bit differs between them. We use that differing bit to split the array into two groups — each group contains exactly one of the unique numbers.
function twoSingleNumbers(nums) {
let xor = 0;
for (const num of nums) xor ^= num; // xor = a ^ b
// find rightmost set bit (where a and b differ)
const diffBit = xor & (-xor);
let a = 0, b = 0;
for (const num of nums) {
if (num & diffBit) a ^= num; // group with bit set
else b ^= num; // group without bit set
}
return [a, b];
}
// twoSingleNumbers([1, 2, 1, 3, 2, 5]) => [3, 5]def two_single_numbers(nums):
xor = 0
for num in nums:
xor ^= num # xor = a ^ b
# find rightmost set bit (where a and b differ)
diff_bit = xor & (-xor)
a, b = 0, 0
for num in nums:
if num & diff_bit:
a ^= num # group with bit set
else:
b ^= num # group without bit set
return [a, b]
# two_single_numbers([1, 2, 1, 3, 2, 5]) => [3, 5]static int[] twoSingleNumbers(int[] nums) {
int xor = 0;
for (int num : nums) xor ^= num; // xor = a ^ b
// find rightmost set bit (where a and b differ)
int diffBit = xor & (-xor);
int a = 0, b = 0;
for (int num : nums) {
if ((num & diffBit) != 0) a ^= num; // group with bit set
else b ^= num; // group without bit set
}
return new int[]{a, b};
}
// twoSingleNumbers([1, 2, 1, 3, 2, 5]) => [3, 5]Time: O(n), Space: O(1). Two passes through the array, no extra data structures.
Quick Reference
Here’s a cheat sheet of handy bit tricks:
| Trick | Code | Why it works |
|---|---|---|
| Check if odd | n & 1 | Last bit is 1 for odd numbers |
| Multiply by 2 | n << 1 | Shifting left adds a zero at the end |
| Divide by 2 | n >> 1 | Shifting right removes the last bit |
| Toggle bit at pos k | n ^ (1 << k) | XOR flips the target bit |
| Set bit at pos k | n | (1 << k) | OR forces the target bit to 1 |
| Clear bit at pos k | n & ~(1 << k) | AND with inverted mask clears it |
| Check bit at pos k | (n >> k) & 1 | Shift it down and check last bit |
| Remove lowest set bit | n & (n - 1) | Subtracting 1 flips all bits up to lowest set |
In simple language, bit manipulation is one of those topics that feels intimidating at first but has a small set of patterns that repeat everywhere. Master XOR properties and n & (n - 1), and we can handle most interview problems.