0

Is there a better way to count the number of ones in a binary number when it is stored in base 10 using python? I have a large array of unsigned ints that are each associated with a mapping of active edges on a graph. I'd like to count the number of active edges, e.g. when the number is converted to binary, how many "1's" are there in the result? The minimal working example is below, but I'm sure it can be done without resorting to a string casting.

A = [0,1,33,2,18,4,12,8,16,32,]
bin_str = '{0:0b}'
B = [bin_str.format(a) for a in A]
count = [len([c for c in b if c=='1']) for b in B]

print A
print B
print count

> [0, 1, 33, 2, 18, 4, 12, 8, 16, 32]
> ['0', '1', '100001', '10', '10010', '100', '1100', '1000', '10000', '100000']
> [0, 1, 2, 1, 2, 1, 2, 1, 1, 1]

Edit: The related question hints at a lookup table, and something that relies on magic bits. It is unclear if those solutions will work for a 64-bit integer (which is the known max for this problem), nor are they python specific.

Community
  • 1
  • 1
Hooked
  • 84,485
  • 43
  • 192
  • 261
  • do you mean counting the ones? – Joran Beasley Jul 25 '14 at 20:57
  • 1
    Note that it'd be much faster if you use string's `count()` method instead of a Python for-loop. – Ashwini Chaudhary Jul 25 '14 at 21:05
  • @Hooked my answer came from that same question thats why I closed it ... its farther down... and contrary to user2599709's comment that its a hacky way to compute ... its fast and it always works (there is a mathematical proof on the other question) ... its much faster than counting bits ... – Joran Beasley Jul 25 '14 at 21:08
  • @JoranBeasley Knowing the proper naming, helped me find this [question](http://stackoverflow.com/a/407758/249341) which gives the nice answer of `bin(x).count('1')` in pure python. – Hooked Jul 25 '14 at 21:15

0 Answers0