Notes › DSA
Bit Manipulation
Computers store integers in binary. Working directly on bits gives very fast, very short solutions to some problems.
13 in binary is 1101 = 8 + 4 + 0 + 1. Bits are numbered from the right, starting at 0.
Operators
| Operator | C++ | Rule | Example (12 = 1100, 10 = 1010) |
|---|---|---|---|
| AND | a & b |
1 if both are 1 | 1000 = 8 |
| OR | a | b |
1 if either is 1 | 1110 = 14 |
| XOR | a ^ b |
1 if they differ | 0110 = 6 |
| NOT | ~a |
flips every bit | ~12 = -13 (two's complement) |
| Left shift | a << k |
multiply by 2ᵏ | 3 << 2 = 12 |
| Right shift | a >> k |
divide by 2ᵏ (floor, for positives) | 12 >> 2 = 3 |
XOR properties (the most useful)
x ^ x = 0andx ^ 0 = x- XOR is commutative and associative → order does not matter.
Single number (every element appears twice except one):
int singleNumber(vector<int>& a) {
int x = 0;
for (int v : a) x ^= v; // pairs cancel out
return x;
}
Missing number in 0..n: XOR all indices and values — what remains is the missing one.
Swap without a temp: a ^= b; b ^= a; a ^= b; (fun fact; don't use it in real code).
Single-bit tricks
| Task | Code |
|---|---|
| Is bit i set? | (x >> i) & 1 |
| Set bit i | x | (1 << i) |
| Clear bit i | x & ~(1 << i) |
| Toggle bit i | x ^ (1 << i) |
| Lowest set bit | x & (-x) |
| Remove lowest set bit | x & (x - 1) |
| Is power of two? | x > 0 && (x & (x - 1)) == 0 |
| Is odd? | x & 1 |
Count set bits
int countBits(int x) { // Brian Kernighan: loops once per set bit
int c = 0;
while (x) { x &= x - 1; c++; }
return c;
}
// built-in: __builtin_popcount(x), __builtin_popcountll(x) for long long
Bitmask subsets
A number from 0 to 2ⁿ − 1 can represent a subset of n items: bit i = 1 means item i is chosen.
void allSubsets(vector<int>& a) {
int n = a.size();
for (int mask = 0; mask < (1 << n); mask++) {
for (int i = 0; i < n; i++)
if (mask & (1 << i)) cout << a[i] << " ";
cout << "\n";
}
}
Bitmask DP (e.g. travelling salesman for n ≤ 20) uses the mask as part of the state.
Two's complement (negative numbers)
-x = ~x + 1. For 8 bits, -1 is 11111111. This is why ~12 = -13.
Gotchas
1 << 31overflows a 32-bitint; use1LL << kfor big shifts.- Operator precedence:
x & 1 == 0meansx & (1 == 0). Always use brackets:(x & 1) == 0. - Right-shifting negative numbers is arithmetic (keeps the sign) in practice.
Classic problems
| Problem | Trick |
|---|---|
| Single number | XOR all |
| Single number II (others appear 3 times) | count each bit mod 3 |
| Two single numbers | XOR, split by lowest set bit |
| Missing number | XOR indices and values |
| Number of 1 bits / counting bits | x & (x-1), dp[i] = dp[i >> 1] + (i & 1) |
| Power of two / four | x & (x-1) |
| Reverse bits | shift out and in 32 times |
| Subsets | bitmask from 0 to 2ⁿ − 1 |
| Maximum XOR of two numbers | trie of bits |
Practise in the Bit Manipulation section.
Interview one-liners
x & (x - 1)removes the lowest set bit — the key to power-of-two and counting bits.- XOR finds the odd one out because equal values cancel.
- Bit operations are O(1); bitmask subset enumeration is O(2ⁿ · n).