Bit Manipulation

Bit Manipulation

Bitwise operations work directly on binary representations. Fast, constant-space tricks.

Operators

| Operator | Symbol | Example | |----------|--------|---------| | AND | & | 5 & 3 = 1 (101 & 011 = 001) | | OR | | | 5 | 3 = 7 (101 | 011 = 111) | | XOR | ^ | 5 ^ 3 = 6 (101 ^ 011 = 110) | | NOT | ~ | ~5 = -6 | | Left shift | << | 2 << 3 = 16 (multiply by 2³) | | Right shift | >> | 16 >> 2 = 4 (divide by 2²) |

Left shift × 1 bit = multiply by 2. Right shift × 1 bit = integer divide by 2.

Core Bit Operations

# Get bit i
(n >> i) & 1          # 1 if bit i is set, 0 otherwise

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

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

# Toggle bit i
n ^ (1 << i)

# Clear the LOWEST set bit (Brian Kernighan trick)
n & (n - 1)

# Isolate the lowest set bit
n & (-n)

Common Tricks

# Check if power of 2 (exactly one bit set)
n > 0 and (n & (n - 1)) == 0

# Count set bits (Brian Kernighan's algorithm)
count = 0
while n:
    n &= (n - 1)    # clears the lowest set bit each iteration
    count += 1

# Simpler (Python-specific)
bin(n).count('1')

# XOR trick: find the ONE unique element (all others appear twice)
def find_unique(arr):
    result = 0
    for x in arr:
        result ^= x
    return result     # a ^ a = 0, so duplicates cancel out

# Swap without temp variable
a ^= b
b ^= a
a ^= b

# Recursive multiplication with bit shifts
def multiply(a, b):
    if b == 0: return 0
    half = multiply(a, b >> 1)      # b // 2
    return half + half if b % 2 == 0 else half + half + a

Two's Complement

Negative numbers in binary: flip all bits, then add 1.

• -1 = all 1s (...11111111)
• -n = ~n + 1
• In Python, integers are arbitrary precision — no overflow risk

XOR Properties (memorise these)

a ^ 0 = a          # XOR with 0 is identity
a ^ a = 0          # XOR with self is 0
a ^ b = b ^ a      # commutative
(a ^ b) ^ c = a ^ (b ^ c)   # associative

XOR is its own inverse — (a ^ b) ^ b = a.

Subset Enumeration with Bitmasks

def all_subsets(arr):
    n = len(arr)
    for mask in range(1 << n):      # 0 to 2^n - 1
        subset = [arr[i] for i in range(n) if mask & (1 << i)]
        print(subset)
# Time: O(2^n × n), useful for small n (≤ 20)

Key Interview Tips

• XOR is your tool for finding a unique/missing element when all others appear in pairs
• Left/right shift is cleaner than writing * 2 or // 2 in bit-manipulation contexts
• n & (n-1) clearing the lowest set bit is useful for counting set bits and power-of-2 checks
• In Python, ~n gives -(n+1) due to two's complement — use with care