patternpythonMinor
Counting the number of bits of a positive integer
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 sSolution
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.
Why is
i.e. there is no relation between
This removes
I see that the result is off by 1 bit, and your code correctly adjust for that. Again, no idea why it does that.
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 <<= 1Why 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 that10000 < 100000 < 101010 < 1000000 < 10000000 < 100000000i.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 += aThis 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 sI 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 <<= 1s = 0
while a>1:
a >>= 1
if n >= 1<<a:
n >>= a
s += aif n>0:
s += 1
return sContext
StackExchange Code Review Q#11181, answer score: 7
Revisions (0)
No revisions yet.