5
\$\begingroup\$

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
\$\endgroup\$
  • 3
    \$\begingroup\$ My silly question :): Cant you use math.floor(math.log(number,2)) + 1? Or do you mean the number of bits set? \$\endgroup\$ – rahul Apr 26 '12 at 0:53
7
\$\begingroup\$

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.

\$\endgroup\$
5
\$\begingroup\$

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

>>> 34809283402483 .bit_length()
45
\$\endgroup\$
  • 3
    \$\begingroup\$ 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. \$\endgroup\$ – I. J. Kennedy Jun 21 '14 at 17:56
3
\$\begingroup\$
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.

\$\endgroup\$
  • \$\begingroup\$ -1 I think that denying to read the code of the OP and posting a own solution is not the intention of code review. \$\endgroup\$ – miracle173 Apr 29 '12 at 8:45
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Konrad Rudolph Apr 29 '12 at 10:51
1
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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'))
\$\endgroup\$
  • \$\begingroup\$ Good, except the OP wants the number of bits, not the number of set bits. (At least that's what his code does) \$\endgroup\$ – Winston Ewert Apr 28 '12 at 17:23
  • 1
    \$\begingroup\$ and [2:] would be (IMO) better written as .lstrip('0b') (self-documenting code, avoid magic numbers, etc) \$\endgroup\$ – ch3ka May 2 '12 at 1:08
0
\$\begingroup\$

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'
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Toby Speight Feb 12 at 9:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.