Bit Manipulation: Tricks, XOR and Bitmasks

Bit manipulation treats an integer as a row of bits and works on all of them at once with AND, OR, XOR, NOT and shifts. Interviews use it in three ways: as a fast trick for a single number (power of two, lowest set bit), as a compact representation of a set (bitmasks), and as the actual topic of the question (count bits, find the unpaired element, add without +).

Intuition

• a & b keeps bits set in both, a | b bits set in either, a ^ b bits set in exactly one, ~a flips every bit.
• x << k multiplies by 2^k; x >> k divides by 2^k rounding down, so -1 >> 1 is -1. Integer division in C++/Java truncates toward zero instead (-1 / 2 == 0), so the two differ for negative numbers.
• Negative numbers use two's complement: -x == ~x + 1. In Python integers are unbounded, so a negative number behaves as if it had infinitely many leading 1 bits, and ~x == -x - 1. To imitate 32-bit behavior, mask with 0xFFFFFFFF.

The two identities behind most tricks:

• x & (x - 1) clears the lowest set bit (10100 -> 10000), because subtracting 1 turns the lowest 1 into 0 and the zeros below it into 1s.
• x & -x isolates the lowest set bit (10100 -> 00100), often called lowbit; Fenwick trees are built on it.

When to use it in interviews / OAs

• "Without using extra space, find the element that appears once" (XOR cancels pairs).
• Power-of-two checks, counting set bits, reversing bits, Hamming distance.
• n <= 20 items and the state is "which items are chosen": represent subsets as integers.
• "Add two integers without + or -", "Gray code", "maximum XOR" style questions.

Template: single-bit operations

def get_bit(x: int, i: int) -> int:
    return x >> i & 1


def set_bit(x: int, i: int) -> int:
    return x | 1 << i


def clear_bit(x: int, i: int) -> int:
    return x & ~(1 << i)


def toggle_bit(x: int, i: int) -> int:
    return x ^ 1 << i


def lowbit(x: int) -> int:
    return x & -x  # lowest set bit: 0b10100 -> 0b100


def clear_lowest(x: int) -> int:
    return x & (x - 1)  # 0b10100 -> 0b10000


def is_power_of_two(x: int) -> bool:
    return x > 0 and x & (x - 1) == 0  # exactly one set bit


def popcount(x: int) -> int:
    count = 0
    while x:  # one iteration per set bit (x >= 0)
        x &= x - 1
        count += 1
    return count

In Python 3.10+ x.bit_count() is the built-in popcount, and x.bit_length() gives the position of the highest set bit plus one.

Counting bits for every number from 0 to n is a one-line DP: i has the bits of i >> 1 plus its last bit.

def count_bits(n: int) -> list[int]:
    bits = [0] * (n + 1)
    for i in range(1, n + 1):
        bits[i] = bits[i >> 1] + (i & 1)  # drop the last bit, then add it back
    return bits

Template: XOR cancellation

a ^ a == 0 and a ^ 0 == a, and XOR is commutative, so XOR-ing a list cancels every value that appears twice. If two values appear once, their XOR is non-zero; any set bit of it separates them into two groups that can be XOR-ed separately.

from functools import reduce
from operator import xor


def single_number(nums: list[int]) -> int:
    return reduce(xor, nums, 0)  # pairs cancel out


def two_single_numbers(nums: list[int]) -> list[int]:
    both = reduce(xor, nums, 0)  # a ^ b, non-zero since a != b
    split = both & -both  # a bit where a and b differ
    a = reduce(xor, (x for x in nums if x & split), 0)
    return [a, both ^ a]

Template: bitmasks as sets

With a universe of n items, a mask is a subset: a | b is union, a & b intersection, a & ~b difference, a ^ b symmetric difference, ((1 << n) - 1) ^ a complement. Three enumeration idioms come up again and again:

def all_subsets(items: list) -> list[list]:
    n = len(items)
    return [[items[i] for i in range(n) if mask >> i & 1] for mask in range(1 << n)]


def submasks(mask: int) -> list[int]:
    out, s = [], mask
    while s:  # every non-empty submask, in decreasing order
        out.append(s)
        s = (s - 1) & mask
    return out


def masks_with_k_bits(n: int, k: int) -> list[int]:
    # Gosper's hack (k >= 1): jump straight to the next integer with the same popcount
    out, x = [], (1 << k) - 1
    while x < 1 << n:
        out.append(x)
        low = x & -x
        ripple = x + low  # carry the lowest block of ones one step to the left
        x = ripple | ((x ^ ripple) >> 2) // low  # put the remaining ones at the bottom
    return out

(s - 1) & mask steps to the next smaller submask: subtracting 1 clears the lowest set bit and sets everything below it, and & mask throws away the bits that are not in mask. Iterating the submasks of every mask of n bits costs O(3^n) in total, which is the backbone of subset DP.

Template: fixed-width arithmetic

Python never overflows, so problems defined on 32-bit integers need explicit masking. Adding without +: XOR gives the sum without carries, AND shifted left gives the carries; repeat until there are no carries.

MASK32 = 0xFFFFFFFF


def to_signed32(x: int) -> int:
    x &= MASK32
    return x - (1 << 32) if x >> 31 else x


def add_without_plus(a: int, b: int) -> int:
    a, b = a & MASK32, b & MASK32
    while b:
        carry = (a & b) << 1  # positions that generate a carry
        a = (a ^ b) & MASK32  # sum ignoring carries
        b = carry & MASK32
    return to_signed32(a)


def reverse_bits(x: int) -> int:
    out = 0
    for _ in range(32):
        out = out << 1 | x & 1
        x >>= 1
    return out

Complexity

Single-bit operations are O(1). Kernighan's popcount loops once per set bit. Counting bits up to n is O(n). Enumerating all subsets is O(2^n * n) when building lists, submasks of one mask O(2^popcount), Gosper's enumeration O(C(n, k)). The add loop runs at most 32 times.

Common pitfalls

• Precedence in C++/Java: x & 1 == 0 means x & (1 == 0). Parenthesize: (x & 1) == 0. In Python comparisons bind looser than bitwise operators, but parentheses are still kinder to readers.
• Shifting past the width: in C++, 1 << 31 overflows a signed int and 1 << 32 is undefined; use 1LL << k or 1ULL << k.
• Signed right shift: >> on negatives is arithmetic (it keeps the sign); Java's >>> is logical. In Python, mask first if you need unsigned behavior.
• Python's infinite sign bits: ~5 == -6, and bin(-5) is -0b101, not a 32-bit pattern. Use x & 0xFFFFFFFF before printing or counting bits of negatives.
• Gosper's hack with k = 0 divides by zero (low is 0); handle the empty set separately.

Interview variations

• Single number (all others twice), single number II (all others three times: count each bit modulo 3), two single numbers.
• Missing number in 0..n: XOR all indices and values.
• Number of 1 bits, counting bits, Hamming distance (popcount(a ^ b)), total Hamming distance (per bit: ones * zeros).
• Power of two / four: one set bit, and for four the bit sits at an even position (x & 0x55555555).
• Subsets via bitmask, maximum product of word lengths (letters as 26-bit masks, words compatible when a & b == 0).
• Sum of two integers without + or -, reverse bits, bitwise AND of a range (common prefix of the two ends).