Chapter 17 of 30
Bit Manipulation & Masking
Master bitwise operators, bit tricks, XOR properties, bitmask enumeration, and builtin functions for competitive programming.
Bitwise OperatorsBit TricksXOR PropertiesBitmask Enumeration__builtin Functions
Share:
Bit Manipulation & Masking
Bit operations are the fastest operations in computing. Bit manipulation is essential for problems involving subsets, masks, parity, and low-level optimization.
Bitwise Operators
| Operator | Name | Example | Result |
|---|---|---|---|
& | AND | 5 & 3 | 1 (0101 & 0011 = 0001) |
| | OR | 5 | 3 | 7 (0101 | 0011 = 0111) |
^ | XOR | 5 ^ 3 | 6 (0101 ^ 0011 = 0110) |
~ | NOT | ~5 | bitwise complement |
<< | Left shift | 1 << 3 | 8 (multiply by 2³) |
>> | Right shift | 8 >> 3 | 1 (divide by 2³) |
Bit Tricks
Check if Bit i is Set
hljs cpp
bool isSet = (n >> i) & 1;
Set Bit i
hljs cpp
n |= (1 << i);
Clear Bit i
hljs cpp
n &= ~(1 << i);
Toggle Bit i
hljs cpp
n ^= (1 << i);
Check if n is a Power of 2
hljs cpp
bool isPow2 = (n > 0) && ((n & (n - 1)) == 0);
Count Set Bits
hljs cpp
int count = __builtin_popcount(n); // for int
long long count = __builtin_popcountll(n); // for long long
Lowest Set Bit
hljs cpp
int lowest = n & (-n);
Clear Lowest Set Bit
hljs cpp
n &= (n - 1);
XOR Properties
a ^ a = 0(self-cancellation)a ^ 0 = a(identity)a ^ b = b ^ a(commutative)(a ^ b) ^ c = a ^ (b ^ c)(associative)
Find the Number That Appears Odd Times
hljs cpp
int result = 0;
for (int x : a) result ^= x;
// All pairs cancel, leaving the unique element
Swap Two Numbers Without Temp
hljs cpp
a ^= b;
b ^= a;
a ^= b;
Find Two Unique Numbers (All Others Appear Twice)
hljs cpp
int xorAll = 0;
for (int x : a) xorAll ^= x;
// xorAll = a ^ b (the two unique numbers)
int lowestBit = xorAll & (-xorAll);
int group0 = 0, group1 = 0;
for (int x : a) {
if (x & lowestBit) group1 ^= x;
else group0 ^= x;
}
// group0 and group1 are the two unique numbers
Bitmask Enumeration
Enumerate all subsets of n elements:
hljs cpp
// All subsets of {0, 1, ..., n-1}
for (int mask = 0; mask < (1 << n); mask++) {
// mask represents a subset
// bit i set → element i is in the subset
for (int i = 0; i < n; i++) {
if (mask & (1 << i)) {
// element i is in this subset
}
}
}
Iterate Over All Submasks
hljs cpp
// All submasks of mask
for (int submask = mask; submask; submask = (submask - 1) & mask) {
// process submask
}
DP on Bitmasks (TSP Example)
hljs cpp
// Traveling Salesman Problem
// dp[mask][i] = minimum cost to visit all cities in mask, ending at i
const int INF = 1e9;
int dp[1 << n][n];
memset(dp, INF, sizeof(dp));
dp[1][0] = 0; // start at city 0
for (int mask = 1; mask < (1 << n); mask++) {
for (int u = 0; u < n; u++) {
if (!(mask & (1 << u))) continue;
if (dp[mask][u] == INF) continue;
for (int v = 0; v < n; v++) {
if (mask & (1 << v)) continue;
int newMask = mask | (1 << v);
dp[newMask][v] = min(dp[newMask][v], dp[mask][u] + dist[u][v]);
}
}
}
int ans = INF;
for (int u = 0; u < n; u++) {
ans = min(ans, dp[(1 << n) - 1][u] + dist[u][0]);
}
__builtin Functions
hljs cpp
__builtin_popcount(n) // number of set bits (int)
__builtin_popcountll(n) // number of set bits (long long)
__builtin_clz(n) // count leading zeros
__builtin_ctz(n) // count trailing zeros
__builtin_parity(n) // parity of set bits (1 if odd)
Summary
- Bitwise operations are O(1) — use them for speed
- XOR cancels identical values — useful for finding unique elements
- Bitmask enumeration: iterate all subsets in O(2ⁿ × n)
__builtin_popcountfor counting set bits- The lowest set bit trick
n & (-n)isolates the rightmost 1
Prefer reading offline? Download the full book as a PDF.
Download Free Book