This is the mail archive of the
gcc-help@gcc.gnu.org
mailing list for the GCC project.
Re: Number of 1's in 64 bit number...[don't read if not interestedin algos/math...]
- From: Wei Qin <wqin at EE dot Princeton dot EDU>
- To: nathan at cs dot bris dot ac dot uk
- Cc: kelley dot r dot cook at gm dot com, Preeti Aira <ms_preeti at hotmail dot com>, gcc <gcc at gcc dot gnu dot org>, gcc-help <gcc-help at gcc dot gnu dot org>
- Date: Thu, 25 Apr 2002 15:12:07 -0400 (EDT)
- Subject: Re: Number of 1's in 64 bit number...[don't read if not interestedin algos/math...]
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
>