Solve problems in O(1) space and O(n) time using XOR tricks, bitmasks, and bitwise operators on binary representations.
Bit manipulation operates directly on the binary representation of integers using operators like AND, OR, XOR, NOT, and bit shifts. Instead of using data structures to track state, we encode information into individual bits, giving us constant space and blazing-fast operations.
Every integer is a sequence of bits. Bitwise operators let us inspect, set, clear, and toggle individual bits in O(1) time. XOR is the star: it cancels duplicates, finds missing values, and swaps without a temp variable.
Why XOR is so powerful: XOR has three magical properties: (1) a ^ a = 0 — any number XOR itself is zero. (2) a ^ 0 = a — any number XOR zero is itself. (3) XOR is commutative and associative, so order does not matter. Together, these properties let us cancel out duplicates in a single pass.
Look for these recognition signals in the problem statement. If you spot one, bit manipulation is very likely the intended approach.
"Find the single/missing element"
"Generate all subsets"
"Count number of 1 bits" or "Hamming weight"
"Without using +/- operators"
The key clue: The problem asks for O(1) extra space with elements that appear in pairs, or involves powers of 2, subsets, or direct binary operations. A hash set or sorting would work but bit manipulation gives you constant space and often a simpler solution.
XOR's self-cancellation property a ^ a = 0 makes it perfect for finding elements that appear an odd number of times. XOR all elements together and duplicates cancel to zero, leaving only the unique value.
Every element appears twice except 4. XOR everything to find it.
Given [3, 0, 1] with n = 3, find the missing number from range [0, 3]. XOR all values and all indices (plus n):
A bitmask uses each bit position to represent a yes/no decision. For an array of n elements, a mask from 0 to 2^n - 1 represents every possible subset. Bit i being set means "include element i."
n = 3 elements means 2^3 = 8 subsets. Each mask is a 3-bit number.
| MASK | BIT 2 (c) | BIT 1 (b) | BIT 0 (a) | SUBSET |
|---|---|---|---|---|
| 000 | 0 | 0 | 0 | { } |
| 001 | 0 | 0 | 1 | { a } |
| 010 | 0 | 1 | 0 | { b } |
| 011 | 0 | 1 | 1 | { a, b } |
| 100 | 1 | 0 | 0 | { c } |
| 101 | 1 | 0 | 1 | { a, c } |
| 110 | 1 | 1 | 0 | { b, c } |
| 111 | 1 | 1 | 1 | { a, b, c } |
(mask >> i) & 1 — returns 1 if bit i is set
mask | (1 << i) — turn bit i on
mask & ~(1 << i) — turn bit i off
mask ^ (1 << i) — flip bit i
n & (-n) — isolate the rightmost 1-bit
n & (n - 1) — turn off the rightmost 1-bit
Choosing the variant: If the problem involves finding unique or missing values among duplicates, use XOR tricks. If the problem involves enumerating combinations, checking permissions, or tracking boolean states, use bitmasks. Many problems combine both.
Here are the annotated templates for the two most common bit manipulation patterns.
// Find the element that appears exactly once int singleNumber(int[] nums) { int result = 0; for (int n : nums) { result ^= n; // XOR cancels duplicates } return result; // only the unique value remains }
// Generate all subsets of nums using bitmask enumeration List<List<Integer>> subsets(int[] nums) { int n = nums.length; List<List<Integer>> result = new ArrayList<>(); for (int mask = 0; mask < (1 << n); mask++) { List<Integer> subset = new ArrayList<>(); for (int i = 0; i < n; i++) { if ((mask >> i & 1) == 1) { // bit i is set subset.add(nums[i]); } } result.add(subset); } return result; }
// Count the number of 1-bits in n int hammingWeight(int n) { int count = 0; while (n != 0) { n &= (n - 1); // clear the lowest set bit count++; } return count; // runs exactly (number of 1-bits) times }
The n & (n - 1) trick: Subtracting 1 from n flips the lowest set bit and all bits below it. ANDing with n clears that lowest set bit. This runs in O(k) where k is the number of set bits — faster than checking all 32 bits one by one.
Let us trace through counting set bits in the number 13 (binary 1101) using the Brian Kernighan trick n & (n - 1).
Each iteration clears the lowest set bit. We count how many iterations until n becomes 0.
| STEP | n (BINARY) | n - 1 | n & (n-1) | COUNT |
|---|---|---|---|---|
| Initial | 1101 | — | — | 0 |
| Iter 1 | 1101 | 1100 | 1100 | 1 |
| Iter 2 | 1100 | 1011 | 1000 | 2 |
| Iter 3 | 1000 | 0111 | 0000 | 3 |
Here is why it works for n = 12 (1100):
Notice the pattern: The Brian Kernighan trick runs in O(k) where k is the number of set bits, not O(32). For sparse numbers (few 1s), this is significantly faster. This is the basis for LeetCode #191 (Number of 1 Bits) and #338 (Counting Bits).
These are classic LeetCode problems that use the bit manipulation pattern, listed in rough order of difficulty.
Practice tip: Start with #136 (direct XOR application) and #191 (n & (n-1) trick). Then try #268 which combines XOR with index-value pairing. Once comfortable, tackle #371 which builds addition from scratch using XOR (sum without carry) and AND + shift (carry).
Enter two numbers and step through a bitwise operation bit by bit. Watch how each bit position is processed and see the result build up from right to left.
XOR-based solutions (Single Number, Missing Number) iterate through the array exactly once, performing a single O(1) bitwise operation per element. The running XOR value is stored in a single integer variable — no hash maps, no sorting, no extra arrays. This gives O(n) time, O(1) space.
Bitmask enumeration (Subsets) generates all 2^n subsets and checks n bits for each one, giving O(2^n * n) time. Space is O(2^n * n) to store all subsets.
Counting bits with Brian Kernighan's trick is O(k) per number where k is the number of set bits. For #338 (Counting Bits for all numbers 0 to n), the total time is O(n) using the DP recurrence bits[i] = bits[i & (i-1)] + 1.
Constant-space advantage: Where a hash set solution uses O(n) space and sorting uses O(n log n) time, the XOR approach achieves both O(n) time and O(1) space simultaneously. This is why interviewers love bit manipulation — it shows you can think beyond standard data structures.
XOR cancels duplicates: a ^ a = 0. This single property solves an entire class of problems — finding unique elements, missing numbers, and detecting single occurrences. XOR everything together and duplicates vanish, leaving only the answer.
Bitmasks encode subsets as integers. An n-element set has 2^n subsets. Each subset maps to a binary number where bit i means "include element i." Iterate from 0 to 2^n - 1 to enumerate all subsets without recursion.
n & (n - 1) clears the lowest set bit. This powers Brian Kernighan's algorithm for counting set bits in O(k) time. It also detects powers of 2 (a power of 2 has exactly one set bit, so n & (n-1) == 0).
Bit manipulation gives O(1) space. Where hash sets and sorting require extra memory or modify the input, bitwise operations work with a handful of integer variables. This makes them ideal for "constant extra space" constraints.
Master the six essential operations. Check, set, clear, toggle a bit, isolate the lowest set bit, and clear the lowest set bit. These six operations combine to solve the vast majority of bit manipulation problems you will encounter in interviews.