How can I get the number of "1"s in the binary representation of a number without actually converting and counting ?
# do something
# I want to MAKE this FASTER (computationally less complex).
c = 0
c += n%2
n /= 2
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.