Bit Operations Cheatsheet
| Operation | Code | Description |
|---|---|---|
| AND | a & b | Both bits must be 1 |
| OR | a | b | Either bit is 1 |
| XOR | a ^ b | Bits differ (1 if different) |
| NOT | ~a | Flip all bits |
| Left Shift | a << k | Multiply by 2^k |
| Right Shift | a >> k | Divide by 2^k (floor) |
| Get bit k | (a >> k) & 1 | Isolate bit at position k |
| Set bit k | a | (1 << k) | Turn on bit k |
| Clear bit k | a & ~(1 << k) | Turn off bit k |
| Toggle bit k | a ^ (1 << k) | Flip bit k |
| Check power of 2 | n & (n-1) == 0 | True if n is 2^k |
| Remove lowest set bit | n & (n-1) | Clears rightmost 1 bit |
| Isolate lowest set bit | n & (-n) | Keeps only rightmost 1 bit |
| Count set bits | __builtin_popcount(n) | Number of 1 bits |
XOR Magic Properties
C++
// XOR properties used in interview problems:
// a ^ 0 = a (identity)
// a ^ a = 0 (self-inverse)
// a ^ b ^ a = b (cancellation)
// a ^ b = b ^ a (commutative)
// (a ^ b) ^ c = a ^ (b ^ c) (associative)
// SINGLE NUMBER: find element that appears once (others appear twice)
int singleNumber(vector<int>& nums) {
int res = 0;
for(int n : nums) res ^= n; // paired nums cancel, single remains
return res;
}
// SWAP without temp variable (classic interview trick)
a = a ^ b;
b = a ^ b; // b = (a^b)^b = a
a = a ^ b; // a = (a^b)^a = b
// COUNT SET BITS using Brian Kernighan's algorithm
int countBits(int n) {
int count = 0;
while(n) { n &= (n-1); count++; } // each iteration removes lowest 1 bit
return count;
}
Interactive: XOR Cancellation (Single Number)
Input [1,2,1,3,2] — XOR all bits column by column. Pairs produce identical bit patterns which cancel to 0. Only the single number's bits survive.
Practice Problems
#136Single NumberEasy
Every element appears twice except one. Find that element. Must be O(n) time, O(1) space.
Pattern: XOR all elements. Pairs cancel (a^a=0). Single element remains.
C++
int singleNumber(vector<int>& nums) {
int res=0;
for(int n:nums) res^=n;
return res;
}
// Time: O(n) Space: O(1)
#191Number of 1 BitsEasy
Count the number of set bits (1s) in a 32-bit unsigned integer.
Pattern: n & (n-1) removes the lowest set bit. Count how many times until n=0.
C++
int hammingWeight(uint32_t n) {
int count=0;
while(n) { n&=(n-1); count++; }
return count;
}
// Time: O(number of 1 bits) Space: O(1)
#338Counting BitsEasy
For each number 0 to n, count the number of 1 bits. Return as array. Must be O(n).
Pattern: DP with bit trick. dp[i] = dp[i >> 1] + (i & 1). Right shift removes lowest bit; add 1 if i is odd.
C++
vector<int> countBits(int n) {
vector<int> dp(n+1, 0);
for(int i=1;i<=n;i++)
dp[i] = dp[i>>1] + (i&1);
return dp;
}
// Time: O(n) Space: O(n)
#268Missing NumberEasy
Array 0..n with one missing. Find it.
Pattern: XOR all indices [0..n] with all values. Missing number remains (everything else cancels).
C++
int missingNumber(vector<int>& nums) {
int res=nums.size();
for(int i=0;i<nums.size();i++) res^=i^nums[i];
return res;
}
// Time: O(n) Space: O(1)
#371Sum of Two IntegersMedium
Add two integers without using + or - operators.
Pattern: XOR gives sum without carry. AND << 1 gives carry. Repeat until no carry.
C++
int getSum(int a, int b) {
while(b) {
int carry = (a&b)<<1; // carry bits shifted left
a = a^b; // sum without carry
b = carry;
}
return a;
}
// Time: O(1) — 32 iterations max Space: O(1)
#137Single Number IIMedium
Every element appears 3 times except one. Find it in O(1) space.
Pattern: Count bits mod 3. For each bit position, if count % 3 ≠ 0, it belongs to the single number.
C++
int singleNumber(vector<int>& nums) {
int ones=0, twos=0;
for(int n:nums) {
ones = (ones^n) & ~twos;
twos = (twos^n) & ~ones;
}
return ones; // ones holds bits seen odd # of times
}
// Time: O(n) Space: O(1)
#260Single Number IIIMedium
Exactly two elements appear once, all others twice. Find both in O(n)/O(1).
Pattern: XOR everything → a^b (pairs cancel). Any set bit of a^b is a position where a and b differ — use the lowest one (x&-x) to split all numbers into two groups; each group XORs down to one answer.
C++
vector<int> singleNumber(vector<int>& nums) {
long long x=0;
for(int n:nums) x^=n; // x = a ^ b
long long lsb = x & (-x); // lowest bit where a,b differ
int a=0, b=0;
for(int n:nums) {
if(n & lsb) a^=n; // group 1: bit set
else b^=n; // group 2: bit clear
}
return {a, b};
}
// Time: O(n) Space: O(1) — pairs cancel inside their group
Bit trick checklist: Power of 2 → n&(n-1)==0. Even/Odd → n&1. LSB → n&(-n). Remove LSB → n&(n-1). XOR for "find unique" or "cancel pairs". Shift for multiply/divide by 2.
Deeper Understanding
🧠 Under the Hood — n & (n−1) clears the lowest set bit
Almost every bit trick reduces to how two's complement represents numbers: -n is ~n + 1, which is why n & -n isolates the lowest set bit, and n − 1 borrows through the trailing zeros, which is why n & (n−1) deletes it. If you can draw these two diagrams from memory, you can re-derive the whole checklist above instead of memorizing it.
⚖️ When to Use / When NOT to Use
✅ Use when "everything appears k times except one" — XOR / bit-counting families
Pairs cancel under XOR; for k=3, per-bit counts mod 3 generalize the trick.
✅ Use when representing subsets of ≤ 64 items (bitmask DP, subset enumeration)
A subset is one integer: membership is a shift+AND, union is OR, iteration is `for(s=m; s; s=(s-1)&m)`.
❌ Avoid when readable arithmetic does the same job
Instead: write `n*2` not `n<<1` in application code — compilers do this for you; save bit tricks for where they change the algorithm.
❌ Avoid shifting signed ints by ≥ width or into the sign bit
Instead: use `unsigned`/`uint64_t` for bit work — `1<<31` on int is UB in C++; write `1u<<31` or `1LL<<40`.
🚫 Common Misconceptions
"x << 1 always equals x × 2"
Only until it overflows — shifting into or past the sign bit of a signed int is undefined behavior in C++, not just wrong. The compiler may assume it never happens.
"~x is the negative of x"
~x is −x − 1 (two's complement: −x = ~x + 1). Mixing these up breaks lowest-bit isolation and mask building.
"XOR tricks need the array sorted or paired up adjacently"
XOR is commutative and associative — order is irrelevant, which is exactly why one pass with an accumulator works on any arrangement.
🎤 Interview Follow-ups
"Count set bits in O(1) per query?"
Hardware popcount (`__builtin_popcount` / std::popcount in C++20). Portable fallbacks: Kernighan's loop (O(#ones)) or a 16-bit lookup table. Mention the trade-off, then use the builtin.
"Iterate all subsets of a mask m — and why is the total 3ⁿ?"
`for(int s=m; s; s=(s-1)&m)` visits every non-empty submask. Across all masks, each element is in / out-of-mask / out-of-submask → 3 states → Σ 2^popcount(m) = 3ⁿ.
"Why does n & (n−1) == 0 test for powers of two?"
A power of two has exactly one set bit; deleting it leaves 0. Edge case: n=0 passes the test but isn't a power of two — guard with n > 0.