From: eyal DOT ben-david AT aks DOT com
To: djgpp AT delorie DOT com
Message-ID: <422564D3.00413EC4.00@aks.com>
Date: Sun, 13 Jul 1997 13:54:21 +0200
Subject: Re: odd or even # of 1's (was: no subject)
Mime-Version: 1.0
Content-type: text/plain; charset=US-ASCII
Precedence: bulk




On Thu, Jul 10, 1997 at 03:21:13PM +0530, Chirayu Krishnappa
(chirayu AT poboxes DOT com) wrote:
>
> hi,
>
> i need to find out if a 4 byte (default) integer has an even number of
1's
> in its binary representation or not. I need to operate on 15Mb data and
do
> it fast. shifts (<<) and & is quite slow. is there some lib. function to
> do this? what is the fastest way to get it done?
>
Hello,

Here are some functions to calculate the number of bits of an integer
value.



Method  1
~~~~~~
Twice faster than shift method (on avg) since the number of
loops == the number of bits.  (from Ratko Tomic)

int  bit_count_1 (long x)
{
     int n = 0;
/*
**  The loop will execute once for each bit of x set, this is in average
**  twice as fast as the shift/test method.
*/
     if (x)
          do
          {
                         n++;
                    x &= (x-1);
          } while (x);

     return n;
}


Method  2
~~~~~~
This Method is even faster than method 1.
(Magic algorithm also by  Ratko Tomic)

int bit_count_2 (long i)
{
     i = ((i & 0xAAAAAAAAL) >>  1) + (i & 0x55555555L);
     i = ((i & 0xCCCCCCCCL) >>  2) + (i & 0x33333333L);
     i = ((i & 0xF0F0F0F0L) >>  4) + (i & 0x0F0F0F0FL);
     i = ((i & 0xFF00FF00L) >>  8) + (i & 0x00FF00FFL);
     i = ((i & 0xFFFF0000L) >> 16) + (i & 0x0000FFFFL);
     return (int)i;
}


You can  implement the count also by table look-up.

For more information about it look at  SNIPPETS home page. This
is a huge collection of useful C code fragments, functions and programs.

http://www.brokersys.com/snippets/


Eyal.