HiveBrain v1.2.0
Get Started
← Back to all entries
patternpythonMinor

Counting the number of bits of a positive integer

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
numberthecountingbitspositiveinteger

Problem

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 11:
        a >>= 1
        if n >= 1>= a
            s += a
    if n>0:
        s += 1

    return s

Solution

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
            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(2n)).

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.

Code Snippets

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

Context

StackExchange Code Review Q#11181, answer score: 7

Revisions (0)

No revisions yet.