Bit Manipulation

The core operators

& (AND) checks bits, | (OR) sets bits, ^ (XOR) toggles bits, ~ flips all bits, and <</>> shift bits — multiplying/dividing by powers of two. These run in a single CPU cycle, making bit tricks extremely fast.

Common recipes

Check/set/clear a bit at position i, and the classic n & (n-1) trick that drops the lowest set bit — handy for counting set bits or checking powers of two.

def get_bit(n, i):
    return (n >> i) & 1

def set_bit(n, i):
    return n | (1 << i)

def clear_bit(n, i):
    return n & ~(1 << i)

def count_set_bits(n):
    count = 0
    while n:
        n &= (n - 1)   # drops the lowest set bit
        count += 1
    return count

def is_power_of_two(n):
    return n > 0 and (n & (n - 1)) == 0

Output:

count_set_bits(11)      # 11 = 0b1011 -> 3
is_power_of_two(16)     # True

XOR to find the lone number

XOR is its own inverse: x ^ x = 0 and x ^ 0 = x. XOR-ing every element cancels out pairs, leaving the single unpaired value.

def single_number(nums):
    result = 0
    for x in nums:
        result ^= x
    return result

Output:

single_number([4, 1, 2, 1, 2])  # 4

When bits save the day

Use bitmasks to represent subsets in DP (e.g. Travelling Salesman), track visited states compactly, or replace a small set of booleans with a single integer for speed.