Bit manipulation
A number is a row of bits, and a handful of operations work on all of them at once. They cancel pairs, count bits in a table and list every subset with a single counter.
Treat a number as a row of switches
In binary, 13 is 1101: 8 + 4 + 1. Bit 0 is the rightmost and is worth 1; bit k is worth 2ᵏ. A bitwise operator works on every bit position at once, in a single machine instruction:
- AND (
&): 1 where both bits are 1.x & 1is the lowest bit. - OR (
|): 1 where either is 1. Sets bits. - XOR (
^, exclusive or): 1 where the bits differ.x ^ x = 0andx ^ 0 = x, and the order doesn't matter, so XOR-ing a list cancels every value that appears twice. - Shifts:
x << kmultiplies by 2ᵏ,x >> kdivides by 2ᵏ and drops the remainder.
A bitmask is a number used as a set: bit j is 1 when item j is in. With n items, the numbers 0 to 2ⁿ − 1 are exactly the 2ⁿ subsets, so counting up visits every subset.
This page's pseudocode has no bit operators, so it writes their arithmetic equivalents: x mod 2 for the lowest bit, floor(x / 2) for a right shift, x × 2 for a left shift, and the first example spells XOR out bit by bit, on 32-bit patterns, so a negative number is first turned into its two's complement and turned back at the end. In a real language each is one operator.
The rule
Reach for bits when the problem is about parity, pairs that cancel, powers of two, or sets of up to about 20 items. Write the binary of a small example by hand first: the trick is usually visible there.
Pairs, parity, powers of two and small sets
Everything appears twice except one value
XOR the whole list: the pairs cancel
Count 1 bits, check a power of two, compare bit patterns
x & (x − 1) clears the lowest 1 bit; a power of two has exactly one
Answers for every number up to n
Reuse the answer for i >> 1, a smaller number already done
Every subset of a small list (n up to about 20)
Count a bitmask from 0 to 2ⁿ − 1
"Without + or −", "in O(1) extra space"
Bits carry the information instead of memory
The number without a twin: XOR cancels pairs
Every number appears twice except one. A hash set would find it with O(n) memory. XOR finds it with none: fold the whole list into one value, and each pair cancels to 0, wherever its two copies sit.
Step | Number | Binary | Running XOR |
|---|---|---|---|
1 | 7 | 111 | 111 (7) |
2 | 3 | 011 | 100 (4) |
3 | 5 | 101 | 001 (1) |
4 | 3 | 011 | 010 (2) |
5 | 7 | 111 | 101 (5) |
The running value means nothing halfway through: it only makes sense once both copies of every pair are in. One pass, O(1) extra space.
Count bits for every number, reusing the half
For each number from 0 to n, count the 1 bits. Counting each from scratch takes O(log i) per number. But i shifted right by one, i >> 1, is i without its lowest bit, and it is smaller, so its count is already in the table. Add back the bit that fell off, i & 1.
One O(1) step per number: O(n) in all. This is dynamic programming where the smaller subproblem is found with a shift.
Every subset from one counter
Recursion & backtracking listed the subsets of a list by choosing in or out for each item. A bitmask does it with a loop: count from 0 to 2ⁿ − 1, and for each number take item j exactly when bit j is 1. The row of bits in the drawing is the bitmask, lowest bit on the left so each bit sits under its item.
2ⁿ masks with n bit checks each: O(n × 2ⁿ), the same as the backtracking version, with no recursion. Masks also serve as compact keys, for example to remember which items a dynamic programming state has used.
The moves to know by heart
- 1(x >> j) & 1 // bit j of x
- 2x | (1 << j) // set bit j
- 3x & ~(1 << j) // clear bit j
- 4x ^ (1 << j) // flip bit j
- 5x & (x − 1) // x without its lowest 1 bit
- 6x & (x − 1) = 0 // x is a power of two (x > 0)
- 7fold XOR over a list // pairs cancel
- 8for mask from 0 to 2ⁿ − 1 // every subset of n items
Counting 1 bits by clearing the lowest one each round, x ← x & (x − 1), loops once per 1 bit instead of once per bit position.
Where bit tricks go wrong
In C, Java and JavaScript, x & 1 == 0 means x & (1 == 0). Always write (x & 1) == 0.
Integers are stored in two's complement: −x is the bits of x flipped, plus 1, so −1 is all ones. Shifting a negative number right keeps it negative in most languages; Java and JavaScript have >>> for a shift that fills with zeros.
JavaScript's bit operators work on 32-bit integers, and 1 << 31 is negative there. Python's integers have no fixed width, so ~x is simply −x − 1.
2ⁿ subsets is about a million at n = 20 and a billion at n = 30. Past the low twenties, a mask loop is too slow.
3 questions
Remember this
- XOR cancels pairs:
x ^ x = 0and the order doesn't matter, so XOR-ing a list leaves the value without a twin. x & (x − 1)clears the lowest 1 bit; a positive power of two becomes 0.- Counting a bitmask from 0 to 2ⁿ − 1 visits every subset of n items, practical up to about 20 items.
Now solve some yourself
Only this topic 0 of 14 solved
- EasyCount the 1 bits in a number
- EasyFewest bacteria to plant so the box reaches x
- EasyThe doll without a pair
- EasyIs it a power of two?
- EasyTurn a lock left or right so it ends at zero
- EasyThe one number missing from 0 to n
- EasyCount the bits where two numbers differ
- EasyReverse the bits of a 32-bit number
- MediumEvery number three times except one
- MediumTwo numbers without a twin
- MediumAdd two numbers without + or −
- MediumAND of every number in a range
- MediumA sequence where neighbors differ in one bit
- MediumFewest bit flips to make a OR b equal c
Mixed with topics you have practiced 0 unlocked
2 more once you have practiced Recursion & backtracking, BFS & DFS. Play one of its examples to the end and solve one of its problems to unlock them.
Problems open on their own sites (LeetCode, Codeforces, CodeChef, AtCoder, CSES) in a new tab. Tick Solved when you get it accepted there; your ticks decide which mixed problems open next.
Next