Python Bit-wise Operation

Question

I found the following codes in a book:

def count_bits(x):
 num_bits = 0
 while x:
 num_bits += x&1
 x >>= 1
return num_bits
print(count_bits(12))

I don't understand this line (num_bits += x&1)

Let's say I input 12 (1100), the first character ("1") gets counted. But then there is a right shift and 1100 becomes 0110. If the counter moves to the second character, won't 1 be counted twice?

• Aziz Alto: For reference, is it "Elements of programming interviews in Python" page 23 :-) ?
• SAKURA: @AzizAlto Yes! I am working through the book right now. One of the authors' name is Aziz, like your handle. is it a coincidence or...?
• Aziz Alto: Purely coincidence! It just happens I was browsing the book through the exact example yesterday, good luck! :-]

Answer 1

x&1 checks if the rightmost bit is 1

so for your example it would do:

1100 & 0001 # 0
0110 & 0001 # 0
0011 & 0001 # 1
0001 & 0001 # 1

and correctly return 2. By right shifting, you count the bits from right to left until the last shift results in 0000 and breaks the loop

Answer 2

1 is 0b0001. ANDing it with 0b1100 results in 0. There is never any duplicated counting.

Answer 3

The code

num_bits += x&1

Checks if the least significant bit is set, if it is set 1 is added to num_bits.

x >>= 1

Then shifts the number right one bit, shifting out the least significant bit.

Finally, the loop condition

while x:

Checks if there are still any bits set in the number, this check fails as the final set bit is shifted out.