Pratik Deoghare - 1 year ago 83

Python Question

How can I get the **number of "1"s** in the binary representation of a number without actually converting and counting ?

e.g.

`def number_of_ones(n):`

# do something

# I want to MAKE this FASTER (computationally less complex).

c = 0

while n:

c += n%2

n /= 2

return c

>>> number_of_ones(5)

2

>>> number_of_ones(4)

1

Answer Source

IMO, a good approach would be to use a look-up table - create a dictionary which converts bytes to number of 1's (you can use the code you posted to generate it, it would only need to run once), and then use something like this:

```
def number_of_ones(n):
sum = 0
while n != 0:
sum += lookup_table[n & 0xff]
n >>= 8
return sum
```

I believe this is a fairly good trade-off between space and running-time.