Snippet: bitcount()

[Klaus Alexander Seistrup]

Eugene Leitl <eugene.leitl at lrz.uni-muenchen.de> wrote:

> Ouch, ouch. That was really _inefficient_. At least you could nybble
> or byte-wise lookup, and there should be lots of bigmask magic which
> does in in O(logN). Consider bitcounting L's.
>
>  > def bitcount(x):
>  >     n = 0
>  >     while x:
>  >         x = x & (x-1)
>  >         n = n + 1
>  >     # end while
>  >     return n
>  > # end def bitcount

I don't know about nybble or byte-wise lookups.  The algorithm above does
the job in O(N) where N is the number of bits in the number, even on huge
numbers -- or, to put it in simple words: it doesn't spend time counting
all the 0's.

Let's consider the two big twin primes:

  BIGP1 = 1706595L * (1L << 11235) - 1L
  BIGP2 = 1706595L * (1L << 11235) + 1L

Both numbers have 3389 digits, BIGP1 has 11243 bits whereas BIGP2 has 10.
If you time the execution you will see that counting the bits in BIGP2 is
*very* close to 11243/10 times faster than counting the bits in BIGP1.

Now, I'm not a mathematician and so it is difficult for me to imagine how
I can come up with an algorithm that is actually faster than only counting
the 1's and essentially ignoring the 0's -- which is what the algorithm
above claims to do -- unless I decide to count several bits at a time, but
I wouldn't know how to construct such a thing.

Please prove me wrong. :-)


Cheers,

  //Klaus

-- 
···[ Magnetic Ink ]·················································· ><> ···
···[ http://www.magnetic-ink.dk/ ]···········································