Masks, and thinking bit by bit

A mask is a number with 1s only at the bits you care about. 1 << k is the mask with only bit k set; if n & (1 << k) is not zero, bit k of n is 1. With a mask you look at one bit of a number, set it (|) or flip it (^).

1def is_power_of_two(n):
2    return n > 0 and (n & (n - 1)) == 0
3 
4lowest = n & -n

Two classics: n & (n - 1) clears the rightmost 1 bit; powers of two have a single 1 bit, so the result comes out 0. And n & -n keeps only the rightmost 1 bit. The n > 0 check is essential: n & (n - 1) is zero for 0 as well, and 0 is not a power of two.

Some problems get easy when you think in bit positions instead of numbers. To count in how many bits all the pairs differ (the Hamming distance) you need not try each pair: at one bit position, if c numbers have that bit as 1 and n - c have it as 0, the number of pairs that differ there is c × (n - c). Add that up over every position. A mask also serves to split numbers into two groups: any bit that is set in the XOR of two different odd ones out (x & -x, for instance) is a bit that tells those two apart; divide the numbers in two by that bit and XOR each group within itself.

Tasks