Counting the number of bits of a positive integer

Question

How can I improve this code for counting the number of bits of a positive integer n in Python?

def bitcount(n):
 a = 1
 while 1<<a <= n:
 a <<= 1
 s = 0
 while a>1:
 a >>= 1
 if n >= 1<<a:
 n >>= a
 s += a
 if n>0:
 s += 1
 return s

• Rahul Gopinath: My silly question :): Cant you use math.floor(math.log(number,2)) + 1? Or do you mean the number of bits set?

Answer 1

The very first thing you should do to improve it is comment it. I'm reading it for almost half an hour and still can't understand what it does. I tested it, and it indeed work as intended, but I have no idea why. What algorithm are you using?

I pointed below parts of the code that aren't clear to me. Since @blufox already presented a simpler way to count bits (that works for non-zero numbers), I won't bother to suggest an improvement myself.

def bitcount(n):
 a = 1
 while 1<<a <= n:
 a <<= 1

Why is a growing in powers of two, while you're comparing 1<<a to n? The sequence you're generating in binary is 10 100 10000 100000000 10000000000000000 ... Take n=101010, and notice that

10000 < 100000 < 101010 < 1000000 < 10000000 < 100000000

i.e. there is no relation between 1<<a and the number of bits in n. Choose a=1<<2, and 1<<a is too small. Choose a=1<<3 and 1<<a is too big. In the end, the only fact you know is that 1<<a is a power of two smaller than n, but I fail to see how this fact is relevant to the task.

 s = 0
 while a>1:
 a >>= 1
 if n >= 1<<a:
 n >>= a
 s += a

This removes a bits from n, while increasing the bit count by a. That is correct, but I fail to understand why the resulting n will still have fewer bits than the next 1<<a in the sequence (since they vary so wildly, by 2**(2**n)).

 if n>0:
 s += 1
 return s

I see that the result is off by 1 bit, and your code correctly adjust for that. Again, no idea why it does that.

Answer 2

There's a bit_length method in Python's int object:

>>> 34809283402483 .bit_length()
45

• I. J. Kennedy: bit_length doesn't count the number of 1 bits, it returns the number of bits needed to represent the integer. For example, your 34809283402483 needs 45 bits but only 28 bits are set.

Answer 3

def bitcount(n):
 count = 0
 while n > 0:
 if (n & 1 == 1): count += 1
 n >>= 1
 return count

I didn’t read your code since, as mgibsonbr said, it’s unintelligible.

For an overview over more sophisticated ways to count bits, refer to the Bit Twittling Hacks page.

• miracle173: -1 I think that denying to read the code of the OP and posting a own solution is not the intention of code review.
• Konrad Rudolph: @miracle173 I think the intention of a review is to learn. And while I agree with you in general, I also agree with mgibsonbr in this instance, that OP’s code isn’t salvageable (I did try to understand the code before posting ...). But if you’d write a detailed critique of the code I’d be more than happy to upvote it.

Answer 4

first of, I'm not really sure what your code does, at least not the first part. I'm also unsure if you wonder of the number of bits set, or the number of actual bits? The code under here does both:

#!/usr/bin/env python
import sys, math
def least_significant_bit_is_set (number):
 return (n & 1 == 1)
n = int (sys.argv[1])
#calculate number of set bits
bits_set = 0
while n > 0:
 if least_significant_bit_is_set (n):
 bits_set += 1
 n = n / 2
print bits_set
n = int (sys.argv[1])
# calculate total number of bits
bits = 0
if n > 0:
 bits = int (math.log (n,2)) + 1
print bits 

the n = n/2 could also be substituted by n >>= 1 to show that we are pushing the integer to the right, thereby loosing the least significant bit

Answer 5

If you consider readibility and maintainability as improvements and performance does not matter, you can rely on python string formatting to bit. That is convert the integer in a bit string and measure length.

len("{0:b}".format(n))

Step by step interpretation:

>>> "{0:b}".format(1234)
'10011010010'
>>> len(_)
11

Update:

"{0:b}".format() can be replaced by bin() built-in functions. Note that bin output is prefixed with "0b", so

len(bin(n).lstrip('0b'))

• Winston Ewert: Good, except the OP wants the number of bits, not the number of set bits. (At least that's what his code does)
• ch3ka: and [2:] would be (IMO) better written as .lstrip('0b') (self-documenting code, avoid magic numbers, etc)

Answer 6

You can replace your function with a much smaller function like the one shown below:

def bit_count(number, accumulator=0):
 while number:
 accumulator += 1
 number >>= 1
 return accumulator

Argument checking is left as an exercise for the reader. You can use the following to verify:

numbers = 1, 23, 456, 7890
total_bits = 0
for n in numbers:
 total_bits = bit_count(n, total_bits)
assert total_bits == sum(map(int.bit_length, numbers)), 'your code is incorrect'

• Toby Speight: You have presented an alternative solution, but haven't reviewed the code. Please edit to show what aspects of the question code prompted you to write this version, and in what ways it's an improvement over the original. It may be worth (re-)reading How to Answer.

Answer 7

It seems like your code is intended to count how many times 1 needs to be doubled (1 << a) to reach the provided value, n. The code works, but the style is convoluted. Noctis Skytower provided a more straight-forward solution. Since the program expects positive integers, the end condition occurs when number is 0. For every iteration in which number is positive, accumulator is incremented by 1, and number is nearly cut in half (number >> 1). Notice that the number of right bit shifts required to set number to 0 is equivalent to the number of bits of the original number.