Bit Manipulation

Reach for it when

• Single number among pairs (XOR cancels)
• Count set bits, reverse bits
• Add without the + operator

Core idea

x ^ x = 0 and x ^ 0 = x, so XOR-ing everything cancels pairs. n & (n - 1) clears the lowest set bit, which counts bits in O(set bits). Addition is XOR (sum without carry) plus AND shifted left (the carry), repeated until no carry remains.

Template · O(number of bits)

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

int countBits(uint32_t n) {
    int count = 0;
    while (n) {
        n &= n - 1;  // drop the lowest set bit
        count++;
    }
    return count;
}

Common pitfalls

• Python integers are unbounded: mask with 0xFFFFFFFF for 32-bit behavior
• Operator precedence: wrap bit expressions in parentheses

Practice · 0 / 8 done

• Counting BitsEasy
• Missing NumberEasy
• Number of 1 BitsEasy
• Reverse BitsEasy
• Single NumberEasy
• Reverse IntegerMedium
• Sum of Two IntegersMedium
• Partition Array Into Two Arrays to Minimize Sum DifferenceHard