Pratik Deoghare Pratik Deoghare - 2 years ago 97
Python Question

How can I check Hamming Weight without converting to binary?

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


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)
>>> number_of_ones(4)

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.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download