Bit Manipulation

How it works

Bit manipulation treats an integer as a row of switches. A handful of operations do most of the work: AND to test or clear bits, OR to set them, XOR to toggle, and shifts to move between positions. Each runs in constant time on the whole word.

XOR is the star. It is its own inverse (x ^ x = 0), and order does not matter, so XOR-ing a list where everything appears twice except one value leaves exactly that value. The same property finds a missing number when you XOR indices with values.

Two identities show up constantly: n & (n - 1) clears the lowest set bit, which lets you count set bits in as many steps as there are ones, and n & -n isolates the lowest set bit. A power of two is a positive n with n & (n - 1) equal to 0.

Bitmasks also encode small sets. With up to 20 items, every subset is an integer from 0 to 2^n - 1, which turns subset enumeration and DP over subsets into simple loops. In JavaScript remember that bitwise operators work on signed 32-bit integers.

How to attack it

1. 1Look for pairs that cancel, parity, powers of two, or a small set that fits in a mask.
2. 2Write down the identity you will rely on (x ^ x = 0, n & (n - 1), n & -n).
3. 3Decide the word size and how negatives behave in your language.
4. 4Loop over bits with shifts and masks rather than string conversions.
5. 5Test with 0, 1, a negative value and the largest allowed value.

Template

A skeleton to adapt, not a solution to paste. Write it from memory a few times.

def single_number(nums):
    # Every value appears twice except one: pairs cancel under XOR.
    acc = 0
    for x in nums:
        acc ^= x
    return acc


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


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


def all_subsets(items):
    n = len(items)
    out = []
    for mask in range(1 << n):           # each mask is one subset
        out.append([items[i] for i in range(n) if mask >> i & 1])
    return out


def bit_ops(x, i):
    test = (x >> i) & 1
    set_bit = x | (1 << i)
    clear_bit = x & ~(1 << i)
    toggle = x ^ (1 << i)
    return test, set_bit, clear_bit, toggle

What it costs