# Prime number module

Emile van Sebille emile at fenx.com
Tue Sep 30 22:11:14 CEST 2003

```"Lulu of the Lotus-Eaters" <mertz at gnosis.cx> wrote:

> Along those lines, what's the quickest way to count bits in Python?
> Maybe someone has a clever idea... something that would run a whole
> bunch faster than my bit mask style above for counting all the "1"s in a
> multibyte string.
>

Probably far from the fastest, but in the tradition that you'll get a better
answer by posting, here's a stab at a python method for counting bits:

import string,time

nibbles = [(w+x+y+z, w*8+x*4+y*2+z)
for w in (0,1) for x in (0,1)
for y in (0,1) for z in (0,1)]

bitcounts = [
(chr(hinibblevalue*16 + lonibblevalue),
hibitcount+lobitcount)
for hibitcount, hinibblevalue in nibbles
for lobitcount, lonibblevalue in nibbles ]

bytes = dict(bitcounts)

xlater = "".join([chr(bitcount) for byte, bitcount in bitcounts])

def bitcount1(bytestr):
return sum([bytes[ii] for ii in bytestr])

def bitcount2(bytestr):
return sum(map(ord, string.translate(bytestr,xlater)))

t=time.time()
bitcount1('a'*100000)
print time.time()-t

t=time.time()
bitcount2('a'*100000)
print time.time()-t

--
Emile van Sebille
emile at fenx.com

```