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.

Like what you read? Give Tomáš Bouda a round of applause.

From a quick cheer to a standing ovation, clap to show how much you enjoyed this story.