-1

Please suggest an efficient algorithm if no such library function exists.

hershey92
  • 783
  • 2
  • 6
  • 17
  • Mathematically there are 'the number' of 1's in any 'the number'. – Preet Sangha Sep 24 '12 at 11:01
  • 3
    I assume you talk about the number of 1s in the representation of the number in a specific number system. Decimal perhaps? Or binary? Both are common, and others are possible. –  Sep 24 '12 at 11:02
  • 1
    The correct term would be 'digits'. "Count the `1` digits in a number" would be a clearer way of expressing your question. – Martijn Pieters Sep 24 '12 at 11:03
  • If you mean counting the ones in the binary representation of a number, take a look at [this](http://stackoverflow.com/q/9829578/566644) question. – Lauritz V. Thaulow Sep 24 '12 at 11:07

3 Answers3

4

something like str(number).count("1") ?

jsbueno
  • 99,910
  • 10
  • 151
  • 209
  • Of course, that's assuming OP is talking about the decimal system (the hamming weight, which is about the binary system, is quite common). –  Sep 24 '12 at 11:05
  • Indeed, but I am guessing this is what the O.P. wants, since there is no information to assert it -- it can be wrong should the O.P. ever clarify the question. – jsbueno Sep 24 '12 at 11:10
  • 3
    Or we could just refuse to answer bad questions instead of guessing. – Wooble Sep 24 '12 at 11:20
3

Something like:

for baseconv in (int, oct, hex, bin):
    as_text = str(baseconv(123456789))
    print as_text, as_text.count('1')
Jon Clements
  • 138,671
  • 33
  • 247
  • 280
2

For the number of '1's in the binary representation, an 8 bit lookup table is quite efficient. eg. for 32 bit numbers

>>> tab=[0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8]
>>> N=123456789
>>> tab[N>>24]+tab[N>>16&255]+tab[N>>8&255]+tab[N&255]
16
John La Rooy
  • 295,403
  • 53
  • 369
  • 502