Technique

Bit Manipulation

Bit manipulation lets you work directly with binary representations. It's fast, uses no extra space, and sometimes produces beautifully elegant solutions that feel like magic.

The Essential Operations

# AND - both bits must be 1
a & b

# OR - at least one bit is 1
a | b

# XOR - exactly one bit is 1
a ^ b

# NOT - flip all bits
~a

# Left shift - multiply by 2^n
a << n

# Right shift - divide by 2^n
a >> n

The Key Insight

XOR is your best friend. a ^ a = 0, a ^ 0 = a. This lets you cancel out pairs and find the odd one out. It's the secret behind many bit manipulation tricks.

Classic: Single Number

Find the element that appears once (others appear twice):

def singleNumber(nums):
    result = 0
    for num in nums:
        result ^= num  # Pairs cancel out!
    return result

Useful Bit Tricks

# Check if n is power of 2
n & (n - 1) == 0

# Get lowest set bit
n & (-n)

# Clear lowest set bit
n & (n - 1)

# Check if bit i is set
(n >> i) & 1

# Set bit i
n | (1 << i)

# Clear bit i
n & ~(1 << i)

# Count set bits
bin(n).count('1')

When to Use Bit Manipulation

Finding unique elements - XOR cancels duplicates
Subsets generation - Each bit = include/exclude
Flags/permissions - Multiple booleans in one int
Power of 2 checks - One-liner
Swap without temp - a ^= b; b ^= a; a ^= b

Pro Tip

Bit manipulation often provides O(1) space solutions. When a problem asks for constant extra space, consider if bits can help.

Bit Manipulation

The Essential Operations

Classic: Single Number

Useful Bit Tricks

When to Use Bit Manipulation

Practice Makes Perfect