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

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

[Preeti Aira]

Hello every body..

Can any body give me the algo for finding number of 1's  (set bits) in a 64 
bit number. Algo with out any loop or recurson.  Should be a reasonably 
efficient and small and giving result in fixed time.

have a nice time
Pret.

_________________________________________________________________
Join the worldÂ’s largest e-mail service with MSN Hotmail. 
http://www.hotmail.com

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

[Alan Modra]

On Thu, Apr 25, 2002 at 10:14:02AM +0530, Preeti Aira wrote:
> 
> Can any body give me the algo for finding number of 1's  (set bits) in a 64 
> bit number. Algo with out any loop or recurson.  Should be a reasonably 
> efficient and small and giving result in fixed time.

You can find such an algorithm in at least two places in the gcc
sources, and also in glibc.  You should be able to find it reasonably
easily using grep.

-- 
Alan Modra
IBM OzLabs - Linux Technology Centre

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

[Vivek Srivastava]

Hi Preeti,

On Thu, 25 Apr 2002, Preeti Aira wrote:
> Can any body give me the algo for finding number of 1's  (set bits) in a 64 
> bit number. Algo with out any loop or recurson.  Should be a reasonably 
> efficient and small and giving result in fixed time.

I don't know why do you ask for an algo without any loops or recursion. As 
far as I can see, it cannot be done without them. So if you're ready to 
incorporate them, here's one algo. It's probably the most efficient one 
possible because it gives the result in O(n) time, where 'n' is the number 
of 1 bits in the number. (Doesn't depend on the size of the number.) i.e. 
for both 10110000 and 0000101100000000, it will tell you that there are 3 
1's in just 3 steps.

Here's the algo:

	Let x be the given number.
	count <-- 0
	while (x > 0)
	do
	    	x <-- x AND (x - 1)
		count <-- count + 1


At the end of this loop, 'count' is the required answer. (Here, AND is the 
bitwise 'and' operator.)

Hope that helps.

Vivek

-- 
Vivek Srivastava
MCA II year
Department of Computer Science
University of Pune

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

[Jaswant]

may be preeti is looking for something like algo below which finds 1's in 36
bit number:

//To count the ones in a 36-bit word:
unsigned count_ones(unsigned36 a)
{
  a = a - (a>>1 & 0333333333333);
  a = a - (a>>1 & 0333333333333);

  // Each octal digit is replaced by number of 1's in it

  a = ((a>>3) + a) & 0070707070707;
  return a % 63;    // casting out 63's
}


----- Original Message -----
From: "Vivek Srivastava" <u2000159@cs.unipune.ernet.in>
To: "Preeti Aira" <ms_preeti@hotmail.com>
Cc: <gcc-help@gcc.gnu.org>; <gcc@gcc.gnu.org>
Sent: Thursday, April 25, 2002 11:06 AM
Subject: Re: Number of 1's in 64 bit number...[don't read if not interested
in algos/math...]


> Hi Preeti,
>
> On Thu, 25 Apr 2002, Preeti Aira wrote:
> > Can any body give me the algo for finding number of 1's  (set bits) in a
64
> > bit number. Algo with out any loop or recurson.  Should be a reasonably
> > efficient and small and giving result in fixed time.
>
> I don't know why do you ask for an algo without any loops or recursion. As
> far as I can see, it cannot be done without them. So if you're ready to
> incorporate them, here's one algo. It's probably the most efficient one
> possible because it gives the result in O(n) time, where 'n' is the number
> of 1 bits in the number. (Doesn't depend on the size of the number.) i.e.
> for both 10110000 and 0000101100000000, it will tell you that there are 3
> 1's in just 3 steps.
>
> Here's the algo:
>
> Let x be the given number.
> count <-- 0
> while (x > 0)
> do
>     x <-- x AND (x - 1)
> count <-- count + 1
>
>
> At the end of this loop, 'count' is the required answer. (Here, AND is the
> bitwise 'and' operator.)
>
> Hope that helps.
>
> Vivek
>
> --
> Vivek Srivastava
> MCA II year
> Department of Computer Science
> University of Pune
>
>

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

[Gerald Pfeifer]

On Thu, 25 Apr 2002, Vivek Srivastava wrote:
>> Can any body give me the algo for finding number of 1's  (set bits) in a 64
>> bit number. Algo with out any loop or recurson.  Should be a reasonably
>> efficient and small and giving result in fixed time.
> I don't know why do you ask for an algo without any loops or recursion. As
> far as I can see, it cannot be done without them.

Of course you can!  Any problem with bounded input size can be trivially
implemented without loops or recursion (though code size will increase
with O(...)).

However, this kind of questions is *not* the scope of this mailing list
which is about developing GCC, not developing *with* GCC!

Gerald
-- 
Gerald "Jerry" pfeifer@dbai.tuwien.ac.at http://www.dbai.tuwien.ac.at/~pfeifer/

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

[kelley.r.cook]

int count (long long x) {

int result;

result =
(x & 0x00000001 ? 1 : 0) +
(x & 0x00000002 ? 1 : 0) +
(x & 0x00000004 ? 1 : 0) +
(x & 0x00000008 ? 1 : 0) +
(x & 0x00000010 ? 1 : 0) +
(x & 0x00000020 ? 1 : 0) +
(x & 0x00000040 ? 1 : 0) +
(x & 0x00000080 ? 1 : 0) +
(x & 0x00000100 ? 1 : 0) +
(x & 0x00000200 ? 1 : 0) +
(x & 0x00000400 ? 1 : 0) +
(x & 0x00000800 ? 1 : 0) +
(x & 0x00001000 ? 1 : 0) +
(x & 0x00002000 ? 1 : 0) +
(x & 0x00004000 ? 1 : 0) +
(x & 0x00008000 ? 1 : 0) +
(x & 0x00010000 ? 1 : 0) +
(x & 0x00020000 ? 1 : 0) +
(x & 0x00040000 ? 1 : 0) +
(x & 0x00080000 ? 1 : 0) +
(x & 0x00100000 ? 1 : 0) +
(x & 0x00200000 ? 1 : 0) +
(x & 0x00400000 ? 1 : 0) +
(x & 0x00800000 ? 1 : 0) +
(x & 0x01000000 ? 1 : 0) +
(x & 0x02000000 ? 1 : 0) +
(x & 0x04000000 ? 1 : 0) +
(x & 0x08000000 ? 1 : 0) +
(x & 0x10000000 ? 1 : 0) +
(x & 0x20000000 ? 1 : 0) +
(x & 0x40000000 ? 1 : 0) +
(x & 0x80000000 ? 1 : 0);
return result;
}

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

[Wei Qin]

First, I see only 32 bits being counted. The top 32 bits seems missing.
Second, this is a very slow implementation. A faster one can be
implemented through table lookup. It takes no masking, no branching.

/*need to generate the table yourself*/
unsigned char mytable[256] = {0, 1, 1, 2, 1, ...};
int count (long long x) {

	int ret;
	union {
		long long val;
		unsigned char s[8];
	} a;

	ret = mytable[a.s[0]];
	ret += mytable[a.s[1]];
	....
	ret += mytable[a.s[7]];

	return ret;
}


On Thu, 25 Apr 2002 kelley.r.cook@gm.com wrote:

> int count (long long x) {
>
> int result;
>
> result =
> (x & 0x00000001 ? 1 : 0) +
> (x & 0x00000002 ? 1 : 0) +
> (x & 0x00000004 ? 1 : 0) +
> (x & 0x00000008 ? 1 : 0) +
> (x & 0x00000010 ? 1 : 0) +
> (x & 0x00000020 ? 1 : 0) +
> (x & 0x00000040 ? 1 : 0) +
> (x & 0x00000080 ? 1 : 0) +
> (x & 0x00000100 ? 1 : 0) +
> (x & 0x00000200 ? 1 : 0) +
> (x & 0x00000400 ? 1 : 0) +
> (x & 0x00000800 ? 1 : 0) +
> (x & 0x00001000 ? 1 : 0) +
> (x & 0x00002000 ? 1 : 0) +
> (x & 0x00004000 ? 1 : 0) +
> (x & 0x00008000 ? 1 : 0) +
> (x & 0x00010000 ? 1 : 0) +
> (x & 0x00020000 ? 1 : 0) +
> (x & 0x00040000 ? 1 : 0) +
> (x & 0x00080000 ? 1 : 0) +
> (x & 0x00100000 ? 1 : 0) +
> (x & 0x00200000 ? 1 : 0) +
> (x & 0x00400000 ? 1 : 0) +
> (x & 0x00800000 ? 1 : 0) +
> (x & 0x01000000 ? 1 : 0) +
> (x & 0x02000000 ? 1 : 0) +
> (x & 0x04000000 ? 1 : 0) +
> (x & 0x08000000 ? 1 : 0) +
> (x & 0x10000000 ? 1 : 0) +
> (x & 0x20000000 ? 1 : 0) +
> (x & 0x40000000 ? 1 : 0) +
> (x & 0x80000000 ? 1 : 0);
> return result;
> }
>
>

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

[Nathan Sidwell]

Wei Qin wrote:
> 
> First, I see only 32 bits being counted. The top 32 bits seems missing.
> Second, this is a very slow implementation. A faster one can be
> implemented through table lookup. It takes no masking, no branching.
> 
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

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

[Gabriel Paubert]

Nathan Sidwell wrote:

> Wei Qin wrote:
> 
>>First, I see only 32 bits being counted. The top 32 bits seems missing.
>>Second, this is a very slow implementation. A faster one can be
>>implemented through table lookup. It takes no masking, no branching.
>>
>>
> I suspect something like...
> int bitson (unsigned long x)
> {   
>   x = (x & 0x55555555) + ((x >> 1) & 0x55555555);


Actually the most clever way of implementing
that step that I know is:

x -= (x>>1)&0x55555555;

This happens to give the correct result for each
pair of bits.

Credit where credit is due: I found this trick on
IBM´s website in their PPC compiler writer´s guide.

	Regards,
	Gabriel.

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

[Wei Qin]

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
>

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

[Richard Henderson]

On Thu, Apr 25, 2002 at 03:12:07PM -0400, Wei Qin wrote:
> On a x86 linux platform, it takes 80% more time than the table lookup one.

On hot cache, maybe.  On cold cache the arithmetic will
definitely be faster.


r~

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

[Wei Qin]

We ran the popcount 10 million times to get the time. So cache is
hot. But we care about speed only when we have to run it a lot of times.
So for speed sensitive application, I would choose to use table
lookup. It's just 256 bytes anyway.

Wei

On Thu, 25 Apr 2002, Richard Henderson wrote:

> On Thu, Apr 25, 2002 at 03:12:07PM -0400, Wei Qin wrote:
> > On a x86 linux platform, it takes 80% more time than the table lookup one.
>
> On hot cache, maybe.  On cold cache the arithmetic will
> definitely be faster.
>
>
> r~
>

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

[Daniel Berlin]

On Thu, 25 Apr 2002, Wei Qin wrote:

> 
> First, I see only 32 bits being counted. The top 32 bits seems missing.
> Second, this is a very slow implementation. A faster one can be
> implemented through table lookup. It takes no masking, no branching.

But unless your compiler does array based optimizations (which gcc 
doesn't, some do, some do and do a pretty darn good job, some don't), a 
table lookup will be slower than a parallelizable/vectorizable masking 
solution like:

#define TWO(c) (0x1u << (c)))
#define MASK(c) (((unsigned long)(-1)) / (TWO(TWO(c)) + 1u))
#define COUNT(x, c) ((x) & MASK(c)) + (((x) >> (TWO(c))) & MASK(c))))

int bitcount (long x)
{
	int i;
	for (i = 0; i < 5; i++)
	 x = COUNT (x, i);
	return x;

}

The macros are just computing the neat masks you normally see here.
Though gcc doesn't seem to turn them into constants (intel's compiler 
does) if you do it in a loop. It does if you just write out

x = COUNT (x, 0);
x = COUNT (x, 1); 
....

Add one iteration/adjust data types approriately for 64 bit 
integers.

You should be able to calculate how fast table lookup is versus the above 
by simply counting cycles.

Assume, best case, that the lookup table is in L1 cache.

See if the number of cycles required to compute the above is < (the 
L1 cache latency) * 8 + the cycles required for the moves and adds.


> /*need to generate the table yourself*/
> unsigned char mytable[256] = {0, 1, 1, 2, 1, ...};
> int count (long long x) {
> 
> 	int ret;
> 	union {
> 		long long val;
> 		unsigned char s[8];
> 	} a;
> 
> 	ret = mytable[a.s[0]];
> 	ret += mytable[a.s[1]];
> 	....
> 	ret += mytable[a.s[7]];
> 
> 	return ret;
> }
> 
> 
> On Thu, 25 Apr 2002 kelley.r.cook@gm.com wrote:
> 
> > int count (long long x) {
> >
> > int result;
> >
> > result =
> > (x & 0x00000001 ? 1 : 0) +
> > (x & 0x00000002 ? 1 : 0) +
> > (x & 0x00000004 ? 1 : 0) +
> > (x & 0x00000008 ? 1 : 0) +
> > (x & 0x00000010 ? 1 : 0) +
> > (x & 0x00000020 ? 1 : 0) +
> > (x & 0x00000040 ? 1 : 0) +
> > (x & 0x00000080 ? 1 : 0) +
> > (x & 0x00000100 ? 1 : 0) +
> > (x & 0x00000200 ? 1 : 0) +
> > (x & 0x00000400 ? 1 : 0) +
> > (x & 0x00000800 ? 1 : 0) +
> > (x & 0x00001000 ? 1 : 0) +
> > (x & 0x00002000 ? 1 : 0) +
> > (x & 0x00004000 ? 1 : 0) +
> > (x & 0x00008000 ? 1 : 0) +
> > (x & 0x00010000 ? 1 : 0) +
> > (x & 0x00020000 ? 1 : 0) +
> > (x & 0x00040000 ? 1 : 0) +
> > (x & 0x00080000 ? 1 : 0) +
> > (x & 0x00100000 ? 1 : 0) +
> > (x & 0x00200000 ? 1 : 0) +
> > (x & 0x00400000 ? 1 : 0) +
> > (x & 0x00800000 ? 1 : 0) +
> > (x & 0x01000000 ? 1 : 0) +
> > (x & 0x02000000 ? 1 : 0) +
> > (x & 0x04000000 ? 1 : 0) +
> > (x & 0x08000000 ? 1 : 0) +
> > (x & 0x10000000 ? 1 : 0) +
> > (x & 0x20000000 ? 1 : 0) +
> > (x & 0x40000000 ? 1 : 0) +
> > (x & 0x80000000 ? 1 : 0);
> > return result;
> > }
> >
> >
> 

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

[David Rasmussen]

I'm amazed to read all these suggestions. The problem is old and 
wellknown. It is usually called Population Count or PopCount. It is used 
in several situations, but the use I know best is from bitboard-based 
chess programs. Do a search of "chess bitboard" in google, and read 
about. The lookup-table is the usual implementation if potability is 
required. There are usually faster methods on a given platform, and some 
CPU's have this as a native instruction.

In chess, the board is often relatively sparse and the following 
implementation is better overall than the lookup-table for such 
programs. It loops one time for each 1-bit:

int PopCount(unsigned long long bitboard)
{
         int count = 0;
         while(bitboard)
         {
                 ++count;
                 bitboard &= bitboard - 1;
         }
         return count;
}