Python Bit-wise Operation

user_8354077 0
Viewed 1220

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?

bitwise-operators python
3 Answers

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

user_88900850

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

Ignacio_Vazquez-Abrams_208620

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.

user_88618540
Related