Bit Manipulation Tricks for Competitive Programming in C++
Set, clear, toggle and test bits, cancel pairs with XOR, count bits with popcount, and enumerate every subset of n ≤ 20 items as a bitmask in C++.
- Course: Competitive Programming study plan
- Module: Bit manipulation
- Kind: Lesson
- Reading time: 15 min
- Runtime: Clang 18 · C++20
What is a bitmask in competitive programming?
A bitmask is an integer used as a set: bit i is 1 when element i is in. Setting, clearing, toggling and testing an element are single operations — x | (1 << i), x & ~(1 << i), x ^ (1 << i), (x >> i) & 1 — and counting from 0 to 2ⁿ − 1 visits every subset of n items exactly once.
Lesson
An integer is a row of bits, and a row of bits is a set: bit i on means element i is in. Every operation on that set is one instruction.
The five one-liners
x | (1 << i) // add element i (set bit i)
x & ~(1 << i) // remove element i (clear bit i)
x ^ (1 << i) // flip element i (toggle bit i)
(x >> i) & 1 // is i in the set? (test bit i)
x & (x - 1) // drop the lowest set bit- Bit 0 is the rightmost. Bit i is worth 2ⁱ.
- Past bit 30, write
1LL << i:1 << 40is undefined behaviour on anint. - Builtins:
__builtin_popcountll(x)counts set bits,__builtin_ctzll(x)counts trailing zeros (not for x = 0). x & -xkeeps only the lowest set bit.
x starts at 0- An int is a row of bits, bit 0 on the right. As a set, bit i is on when element i is in. Start with the empty set, x = 0.
- x |= 1 << 1 sets bit 1: OR with a mask holding only that bit turns it on and leaves the rest alone. x = 2.
- x |= 1 << 3 sets bit 3, worth 8: 2 + 8 = 10. The mask now holds the set {1, 3}.
- x |= 1 << 5 adds element 5. x = 42 = 0b00101010, the set {1, 3, 5} in one integer.
- x ^= 1 << 1 toggles bit 1: it was on, so it goes off. 42 becomes 40. Toggling again would bring it back.
- Testing reads, never writes: (x >> 3) & 1 = 1, so 3 is in the set; (x >> 1) & 1 = 0, so 1 no longer is.
- x &= x − 1 clears the lowest set bit: 40 & 39 = 32. Repeat it until x is 0 and you have counted the set bits — popcount(40) = 2.
XOR cancels pairs
x ^ x = 0,x ^ 0 = x, and the order does not matter.- So XOR of a list where every value appears twice except one is that one — O(n) time, O(1) memory.
- Per-bit thinking: a pair differs in bit b when one has a 1 there and the other a 0. With c ones, that is c · (n − c) pairs — summing over bits replaces an O(n²) loop over pairs.
Every subset is a mask
n ≤ 20 in the constraints is a hint: 2²⁰ ≈ 10⁶ subsets.
for (int mask = 0; mask < (1 << n); ++mask) {
ll s = 0;
for (int i = 0; i < n; ++i)
if ((mask >> i) & 1) s += a[i];
// use the subset's sum s
}- Counting from 0 to 2ⁿ − 1 visits every pattern of n bits once: every subset, the empty one included.
- Cost O(2ⁿ · n) ≈ 2 × 10⁷ for n = 20.
nums = [3, 5, 6], target 11- Bit i of a mask says whether nums[i] is chosen. mask 0 has no bits on: the empty subset, sum 0. The target is 11.
- mask 1 = 001 in binary picks {3}, sum 3.
- mask 2 = 010 in binary picks {5}, sum 5.
- mask 3 = 011 in binary picks {3, 5}, sum 8.
- mask 4 = 100 in binary picks {6}, sum 6.
- mask 5 = 101 in binary picks {3, 6}, sum 9.
- mask 6 = 110 in binary picks 5 and 6: 5 + 6 = 11, the target. Count it.
- mask 7 = 111 in binary picks {3, 5, 6}, sum 14, over the target.
- Counting 0 to 2ⁿ − 1 = 7 visits every subset exactly once: 1 of 8 hit 11. Cost O(2ⁿ · n), fine for n ≤ 20 — about 2×10⁷ steps.
More practice
- Single Number — XOR the list.
- Number of 1 Bits — popcount by hand.
- Counting Bits — popcount of i from i >> 1.
- Subsets — masks from 0 to 2ⁿ − 1.
- Total Hamming Distance — count per bit.
Common questions
How do I iterate over all subsets with bitmasks?
Loop for (int m = 0; m < (1 << n); ++m) and treat bit i of m as "element i is chosen", tested with (m >> i) & 1. That visits all 2ⁿ subsets once each, so with an O(n) body it fits for n up to about 20.
Why does XOR find the number that appears once?
XOR is commutative and associative, x ^ x = 0 and x ^ 0 = x. XOR-ing every value lets each pair cancel wherever its two copies sit, leaving only the unpaired value — in O(n) time and O(1) memory.
What does x & (x - 1) do?
It clears the lowest set bit of x. Subtracting 1 turns that bit off and every zero below it on; AND keeps only the bits both share. It counts set bits in a loop and tests for a power of two: x > 0 and x & (x − 1) == 0.
When do I need 1LL << i instead of 1 << i?
Whenever i can be 31 or more. The literal 1 is an int, so 1 << 40 shifts past its 32 bits, which is undefined behaviour, before any conversion to long long. Use 1LL << i and __builtin_popcountll for 64-bit masks.
Exercises
The odd one out
Every value in the list appears exactly twice — except one, which appears once. Print it.
Constraints: n is odd, 1 ≤ n < 2·10⁵, 1 ≤ aᵢ ≤ 10¹⁸. Use O(1) extra memory.
Input: n, then the n values. Output: the value that appears once.
5
4 1 2 1 2prints
4Subsets that hit the target
Count the subsets of the n numbers whose sum is exactly T. The empty subset has sum 0; equal numbers in different positions are different elements.
Constraints: 1 ≤ n ≤ 20, 1 ≤ aᵢ ≤ 10⁹, 0 ≤ T ≤ 2·10¹⁰.
Input: n T, then the n numbers. Output: the number of subsets.
3 11
3 5 6prints
1(only {5, 6}.)
In this module: Bit manipulation
← Checkpoint — Prefix sums and difference arrays · Checkpoint — Bit manipulation →