deepSWE.io

Bit Manipulation Cheat Sheet

Bit manipulation problems aren't the most common in interviews, but they do come up. When they do, they can be tricky. DeepSWE recommends you learn the foundational bit manipulation tricks, as this will help you solve pretty much any bit manipulation problem.

Bitwise Operators Reference

&AND

1 if both bits are 1

1010 & 1100 = 1000

|OR

1 if either bit is 1

1010 | 1100 = 1110

^XOR

1 if bits are different

1010 ^ 1100 = 0110

~NOT

Flips all bits

~1010 = 0101

<<Left Shift

Shift bits left (multiply by 2)

1010 << 1 = 10100

>>Right Shift

Shift bits right (divide by 2)

1010 >> 1 = 0101

Essential Bit Tricks

Check if Bit is Set

n & (1 << i)

Check if the i-th bit is 1

5 & (1 << 2) = 101 & 100 = 100 ≠ 0 → bit 2 is set

bool isBitSet(int n, int i) {
  return (n & (1 << i)) != 0;
}

Set Bit

n | (1 << i)

Set the i-th bit to 1

5 | (1 << 1) = 101 | 010 = 111 = 7

int setBit(int n, int i) {
  return n | (1 << i);
}

Clear Bit

n & ~(1 << i)

Set the i-th bit to 0

7 & ~(1 << 1) = 111 & 101 = 101 = 5

int clearBit(int n, int i) {
  return n & ~(1 << i);
}

Toggle Bit

n ^ (1 << i)

Flip the i-th bit

5 ^ (1 << 1) = 101 ^ 010 = 111 = 7

int toggleBit(int n, int i) {
  return n ^ (1 << i);
}

Rightmost Set Bit

n & -n

Isolate the rightmost set bit

12 & -12 = 1100 & 0100 = 0100 = 4

int rightmostSetBit(int n) {
  return n & -n;
}

Clear Rightmost Set Bit

n & (n - 1)

Remove the rightmost set bit

12 & 11 = 1100 & 1011 = 1000 = 8

int clearRightmostSetBit(int n) {
  return n & (n - 1);
}

Count Set Bits

Brian Kernighan's

Count number of 1s efficiently

n = 12 → 1100 has 2 set bits

int countBits(int n) {
  int count = 0;
  while(n > 0) {
    n &= (n - 1);
    count++;
  }
  return count;
}

Check Power of 2

n & (n - 1) == 0

Check if n is a power of 2

8 & 7 = 1000 & 0111 = 0000 → 8 is power of 2

bool isPowerOfTwo(int n) {
  return n > 0 && (n & (n - 1)) == 0;
}

LeetCode Patterns

XOR Swap

Swap two numbers without temp variable

a ^= b; b ^= a; a ^= b;

Space-efficient swapping

Find Single Number

All numbers appear twice except one

int result = 0; for(int x : nums) result ^= x;

XOR cancels duplicate numbers

Missing Number

Find missing number in range [0, n]

int missing = n; for(int i = 0; i < n; i++) missing ^= i ^ nums[i];

XOR properties for missing elements

Reverse Bits

Reverse all bits in a number

result = (result << 1) | (n & 1); n >>= 1;

Bit-by-bit reversal

Advanced Techniques

Bit Masking

Use bits to represent subsets and states

for(int mask = 0; mask < (1 << n); mask++) // All subsets

Perfect for DP on subsets, traveling salesman

Gray Code

Sequence where adjacent numbers differ by one bit

grayCode(i) = i ^ (i >> 1)

Useful for optimization problems

Bit Hacks

Sign of integer:

sign = (x >> 31) | ((unsigned)(-x) >> 31)

Absolute value (if no overflow):

abs = (x + (x >> 31)) ^ (x >> 31)

Min/Max without branching:

min = y ^ ((x ^ y) & -(x < y))

Fast Math with Bits

x << 1 ≡ x * 2

x >> 1 ≡ x / 2

x & 1 ≡ x % 2

x & (x-1) ≡ clear lowest set bit

x | (x+1) ≡ set lowest unset bit

Notable LeetCode Problems

Easy

• Single Number (136)

• Number of 1 Bits (191)

• Power of Two (231)

• Missing Number (268)

• Reverse Bits (190)

Medium

• Single Number II (137)

• Bitwise AND of Range (201)

• Sum of Two Integers (371)

• Counting Bits (338)

• Gray Code (89)

Hard

• Maximum XOR (421)

• Count Different Bits (461)

• Minimum XOR (1879)

• Find Duplicate (287)*

• N-Queens II (52)*

* Uses bit masking optimization