Bit tricks in interviews

Three rules of XOR

• x ^ 0 = x: XOR with 0 changes nothing.
• x ^ x = 0: a number XOR itself cancels out.
• Order does not matter: a ^ b ^ c is the same in any order and any grouping.

Together they mean: if you XOR a list in which every value appears twice except one, all the pairs cancel and only the lonely value remains.

Single number

Problem: every number in a list appears exactly twice, except one. Find it. A dictionary of counts works in O(n) time but uses O(n) extra space. XOR-ing everything gives the answer in O(n) time and O(1) extra space.

from functools import reduce
from operator import xor

nums = [4, 1, 2, 1, 2]
print(reduce(xor, nums, 0))   # Output: 4

Missing number

Problem: a list holds n different numbers from 0 to n, so exactly one is missing. The sum way: the numbers 0..n add up to n(n + 1)/2, so the missing one is that total minus sum(nums). The XOR way: XOR all of 0..n together with all of nums; every present number appears twice and cancels, leaving the missing one. In Python the sum cannot overflow, but in languages with 32-bit ints a big sum can, while XOR never does.

All subsets with bitmasks

A set of n items has 2ⁿ subsets. Number them with masks from 0 to 2ⁿ − 1, that is range(1 << n). In mask, bit i says whether item i is in the subset. Counting through the masks lists every subset exactly once, with no recursion. The cost is O(n × 2ⁿ), the same as backtracking (Module 5), because the output itself has that size. It is practical only for small n, about 20 or less.

items = ["a", "b", "c"]
n = len(items)
for mask in range(1 << n):
    subset = [items[i] for i in range(n) if mask & (1 << i)]
    print(f"{mask:03b}", subset)
# Output:
# 000 []
# 001 ['a']
# 010 ['b']
# 011 ['a', 'b']
# 100 ['c']
# 101 ['a', 'c']
# 110 ['b', 'c']
# 111 ['a', 'b', 'c']

Hamming distance

The Hamming distance between two numbers is the number of bit positions where they differ. XOR puts a 1 exactly where the bits differ, so the distance is the popcount of x ^ y. It is used in error-detecting codes and for comparing short "fingerprints" of files or images.

Gray code in one line

In a Gray code sequence, neighbouring numbers differ in exactly one bit. The i-th Gray code is i ^ (i >> 1): for i = 0, 1, 2, 3 it gives 0, 1, 3, 2, which is 00, 01, 11, 10. Rotary position sensors use Gray codes so that a reading taken between two positions is never wildly wrong.

Swapping without a temporary variable

a, b = 5, 9
a ^= b
b ^= a
a ^= b
print(a, b)   # Output: 9 5

This XOR swap is a nice puzzle but a bad habit in real code. It is harder to read, it is usually no faster on modern hardware, and if both names refer to the same memory location (for example swapping arr[i] with arr[j] when i == j), it sets the value to 0.

Preview: bitmask dynamic programming

A mask can also stand for "which items have I used so far". For example, the cheapest tour through n cities can be solved with a table indexed by (mask of visited cities, current city) in O(2ⁿ × n²) time, which is practical for n up to about 20. Module 11 covers dynamic programming.

Common mistakes

• Using the XOR trick when the other numbers appear three times. Pairs cancel; triples do not. Fix: count bits per position modulo 3, or use a dictionary.
• Writing mask & i instead of mask & (1 << i) when testing bit i. Fix: always build the mask with a shift.
• Writing 2 ^ n for 2ⁿ. Fix: 1 << n or 2 ** n.
• Hamming distance with negative numbers in Python: x ^ y can be negative, and bin() then hides the bit pattern. Fix: keep inputs non-negative, or mask both with & 0xFFFFFFFF.
• Using XOR swap on two names that may refer to the same element. Fix: use a normal swap.