Counting 1 bits could be done recursivly

Éric DÉTREZ

1

Sure you can. Let’s take your code.

def count_1bits(n):

if n == 0:

return 0

elif n%2 == 0:

return count_1bits(n//2)

else:

return 1 + count_1bits(n//2)

Notice the condition. If `n%2`

is `1`

, return `1 + count1s()`

, otherwise return `0 + count1s()`

. Hence, you can simplify.

def count_1bits(n):

if n == 0:

return 0

else:

return n%2 + count_1bits(n//2)

You can also avoid counting of zeros, as I mentioned in the article, just count ones by eliminating the 1-bit on the right.

def count_1bits(n):

if n == 0:

return 0

else:

return 1 + count_1bits(n & (n - 1))

And there are also some cheap tricks in Python for lazy programmers :-)

def count_1bits(n):

return n and 1 + count_1bits(n & (n - 1))

Here’s your recursive code.