Mail Archives: djgpp/1997/07/13/06:59:24
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.
- Raw text -