Our adventures in Python begin with a program to count the bits set to 1 in a positive integer, using shifting and masking.
def count_bits(x): num_bits = 0 while x: num_bits += x & 1 x >>= 1 return num_bits
The bitwise operators and what they are doing may not be immediately obvious to those coming from a world of arithmetic operators.
x & 1 performs a 'bitwise and': that is to say, outputs a new value based on the corresponding bits of the two incoming values, each of whose bits is set to 1 if and only if that bit is 1 in both incoming values. Given that the second value we are passing in is 1, that means we effectively care only about the rightmost bit of
x here, as every other bit will be
& 0 and therefore 0 by definition.
If the rightmost bit of
x is 1, we'll get a result of 1 and add this to
num_bits gets incremented (or not) by 0. (In binary, all odd numbers have a rightmost digit/bit of 1 and all even numbers have 0 there.)
But we don't want to count only the rightmost bit. Here's where the
>> or rightward shift operator comes in. It shifts each bit in the binary value n places, in this case 1 place, to the right.
>>> 1 >> 1 0 >>> 2 >> 1 1 >>> 3 >> 1 1 >>> 4 >> 1 2 >>> 8 >> 1 4
As we can see, if a single bit is shifted right we are simply left with no bits, i.e. 0. If either 2 (0b10) or 3 (0b11) shifts right we lose the least significant digit and are left with 0b1. 4 (0b100) becomes 2 (0b10) and 8 (0b1000) becomes 4. It is clear that
x >>= 1 is equivalent to
x //= 2.
count_bits function therefore keeps shifting bits rightward, checking each time for a 1, until the integer has been reduced to 0 and
while x therefore ceases to be truthy. O(1) computation per bit equals O(n) time complexity, where n is the number of bits in the integer. No doubt we can do better from here!