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`, otherwise `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`.

Our `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!