Re: Number of 1's in 64 bit number...[don't read if not interested in algos/math...]

[Wei Qin <wqin@EE.Princeton.EDU>]

This is very interesting code. A friend of mine tried it for 64bit
popcount and compared it with the tablelook up one. He inlines the
function and run the 32 bit bitson twice.
On a x86 linux platform, it takes 80% more time than the table lookup one.
I have seen some more interesting code which does

int popcount(unsigned long long x) {

#define TWO(k) (BIGONE << (k))
#define CYCL(k) (BIGNONE/(1 + (TWO(TWO(k)))))
#define BSUM(x,k) ((x)+=(x) >> TWO(k), (x) &= CYCL(k))

  x = (x & CYCL(0)) + ((x>>TWO(0)) & CYCL(0));
  x = (x & CYCL(1)) + ((x>>TWO(1)) & CYCL(1));
  BSUM(x,2);
  BSUM(x,3);
  BSUM(x,4);
  BSUM(x,5);
}

But it is even slower.


Wei


On Thu, 25 Apr 2002, Nathan Sidwell wrote:

> >
> I suspect something like...
> int bitson (unsigned long x)
> {
>   x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
>   x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
>   x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);
>   x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF);
>   x = (x & 0x0000FFFF) + ((x >> 16) & 0x0000FFFF);
>   return x;
> }
> might be better (you can extend that to long long quite simply), and
> some of those later masks will be unnecessary as you can prove carry
> won't happen
>
> nathan
>
> --
> Dr Nathan Sidwell :: Computer Science Department :: Bristol University
>            The voices in my head told me to say this
> nathan@acm.org  http://www.cs.bris.ac.uk/~nathan/  nathan@cs.bris.ac.uk
>