Bit manipulation tricks for CP
Scenario
You need to check if a number is a power of 2. You write a while loop that continuously divides the number by 2. It's O(log N). A senior engineer replaces it with a single, incomprehensible line of symbols that runs in O(1).
How can manipulating raw binary bits replace loops and division?
Why it exists
Bitwise operations map directly to the CPU's ALU (Arithmetic Logic Unit). An integer modulo or division operation might take 10-20 CPU cycles, while a bitwise AND or Shift takes 1 cycle. In systems programming, cryptography, and competitive programming, this 10x hardware acceleration is heavily exploited to optimize bottlenecks.
Mental model
Numbers in a CPU are just arrays of light switches (bits). Arithmetic operations (addition, division) are complex mechanical processes that flip many switches. Bitwise operators are direct electrical wiring: they force individual switches on or off instantly.
Bit manipulation involves using bitwise operators (`&`, `|`, `^`, `~`, `<<`, `>>`) to evaluate logic at the bare-metal level. In CP and technical interviews, these tricks are used to achieve O(1) performance for tasks that would normally require loops or modulo arithmetic.
Explanation
**The Core Operators:**
- **AND (`&`)**: 1 if both bits are 1.
- **OR (`|`)**: 1 if either bit is 1.
- **XOR (`^`)**: 1 if bits are DIFFERENT. XOR is commutative and associative. (Crucial properties: `x ^ x = 0` (cancels itself) and `x ^ 0 = x`).
- **NOT (`~`)**: Inverts all bits (0 becomes 1, 1 becomes 0).
- **Shifts (`<<`, `>>`)**: `1 << n` shifts a 1 to the left by `n` positions. This is equivalent to `2^n`. `x >> 1` is integer division by 2.
**Common CP Tricks:**
1. **Check if Even/Odd:** `(x & 1)` is 1 if odd, 0 if even. Much faster than `x % 2 != 0`.
2. **Multiply/Divide by 2:** `x << 1` multiplies by 2. `x >> 1` divides by 2 (specifically for positive integers, as negative right-shifts round to negative infinity).
3. **Set the i-th bit to 1:** `x = x | (1 << i)`
4. **Check if i-th bit is 1:** `if (x & (1 << i))`
5. **Check if Power of 2:** `x > 0 && (x & (x - 1)) == 0`. (If x is 8 `1000`, x-1 is 7 `0111`. ANDing them yields 0). We must check `x > 0` because `0 & -1` is also 0.
6. **Strip the lowest set bit:** `x = x & (x - 1)` (Crucial for counting set bits).
**GCC Built-in Functions:**
C++ compilers offer blazing-fast hardware-level intrinsics.
- `__builtin_popcount(x)`: Returns the number of 1-bits in `x` (Hamming weight).
- `__builtin_clz(x)`: Counts leading zeros.
- `__builtin_ctz(x)`: Counts trailing zeros.
Code examples
Bitwise Operations
#include <iostream>
int main() {
int x = 44; // Binary: 101100
// Check if odd
bool is_odd = (x & 1);
// Toggle the 2nd bit (0-indexed)
// (1 << 2) is 000100. XOR toggles it.
x = x ^ (1 << 2); // Now 101000 (40)
// Check if power of 2 (false for 40)
bool is_pow_2 = (x > 0) && ((x & (x - 1)) == 0);
// Count set bits (returns 2 for 101000)
int set_bits = __builtin_popcount(x);
return 0;
}These operations compile down to single CPU instructions, making them the fastest operations possible in C++.
Key points
- Use 1LL for large shifts: Always use `1LL << i` if `i` can be greater than 31.
- XOR cancels itself: `A ^ A = 0` is one of the most useful properties in interview questions.
Common mistakes
- Shifting past 32 bits on a standard integer: If you write `1 << 40`, you might expect a large number. But standard `1` is a 32-bit signed integer. Shifting it 40 times is Undefined Behavior and yields garbage. For large masks, you must use a 64-bit literal: `1LL << 40`.
Recall questions
- What does the expression `x & (x - 1)` do to the binary representation of `x`?
- What is the O(1) bitwise expression to check if a positive integer `x` is a power of 2?
- What does `__builtin_popcount(x)` do?
Questions & answers
You have an array where every number appears exactly twice, except for one number which appears exactly once. How can you find the unique number in O(N) time and O(1) space?
XOR all the numbers together. Because `x ^ x = 0`, all pairs will cancel each other out to 0. The remaining value will be the single unique number, since `0 ^ y = y`.
Approach: Identify the cancelling property of the XOR operator.
A developer tries to check if a specific bit `i` is set in a 64-bit integer using `(x & (1 << i))`. For `i = 45`, it incorrectly returns 0 even though the bit is 1. Why?
Because the literal `1` is a 32-bit integer. Shifting it 45 times results in undefined behavior (usually wrapping around or resolving to 0). You must use `1LL << i` to ensure the mask is 64-bit.
Approach: Recognize default literal types and shifting limits.