Pattern 26 of 27

Bit Manipulation

Work directly on binary representations with XOR, AND and shifts to count, cancel or rebuild values without extra memory.

Cost: O(n) or O(number of bits) time, O(1) space
Problems: 6

When to reach for it

The prompt says every element appears twice except one.
You need to count, reverse or test individual bits.
O(1) extra space is expected where a hash set would be the obvious answer.

How it works

A handful of identities cover most interview bit questions. x XOR x is 0 and x XOR 0 is x, so XOR across all elements cancels every pair. x AND (x - 1) clears the lowest set bit, which counts the ones in as many steps as there are ones. Shifting right by one links a number's bit count to a smaller number already computed, which gives Counting Bits in linear time. Summing each bit position modulo 3 handles the variant where the other numbers appear three times.

The template

Written for Single Number (write-up)

def single_number(nums):
    result = 0
    for x in nums:
        result ^= x                   # pairs cancel: a ^ a == 0
    return result

Open in the editor Trace it line by line

Six problems, in learning order

1.Single NumberLeetCode 136XOR everything together.Easy
2.Single Number IILeetCode 137Count each bit position modulo 3.Not in the curated 370 yet.Medium
3.Number of 1 BitsLeetCode 191n & (n - 1) removes one set bit per step.Easy
4.Counting BitsLeetCode 338bits[i] = bits[i >> 1] + (i & 1).Easy
5.Missing NumberLeetCode 268XOR every index and value together; the missing number is what remains.Easy
6.Reverse BitsLeetCode 190Shift the result left and add n's lowest bit, 32 times.Easy

What usually goes wrong

Python integers are unbounded, so 32-bit tricks need explicit masking.
Operator precedence: == binds tighter than & in several languages.
Right-shifting negative numbers behaves differently from language to language.