Mail Archives: djgpp/1997/07/13/16:09:34
"Chirayu Krishnappa (chirayu AT poboxes DOT com)"
<chirayu AT giasbga DOT vsnl DOT net DOT in> wrote:
>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?
The general principal I use for this type of thing is that it is
faster to do a look up than to calculate.
For a single byte you can create table that holds the results for
all combinations. This takes 256 bytes:
const unsigned char PreCalculatedParity[256] = {
0,1,1,0,1,0,0,1,1, 0,0,1,0,1,1,0, 1,0,0,1,0,1,1,0, 0,1,1,0,1,0,0,1,
1,0,0,1,0,1,1,0,0, 1,1,0,1,0,0,1, 0,1,1,0,1,0,0,1, 1,0,0,1,0,1,1,0,
1,0,0,1,0,1,1,0,0, 1,1,0,1,0,0,1, 0,1,1,0,1,0,0,1, 1,0,0,1,0,1,1,0,
0,1,1,0,1,0,0,1,1, 0,0,1,0,1,1,0, 1,0,0,1,0,1,1,0, 0,1,1,0,1,0,0,1
};
If you want to lookup the parity of a value that may be larger
than 8 bits then either make this table larger (however the
memory requirements will grow rather alarmingly) or do the
lookup 8 bits at a time and XOR the results. You should end
up with a bit of code that looks something like:
int ParityOfLong ( unsigned long *mask )
{
return PreCalculatedParity[ ((unsigned char *)mask)[0] ] ^
PreCalculatedParity[ ((unsigned char *)mask)[1] ] ^
PreCalculatedParity[ ((unsigned char *)mask)[2] ] ^
PreCalculatedParity[ ((unsigned char *)mask)[3] ];
}
You should note a few things: Firstly that I'm away from my
work computer so I can't test this. Secondly I use "unsigned"
a lot because of the way C likes to introduce (int) casts in
anything involving math, so this stops sign-extention from
rearing it's ugly head. And finally I write almost exclusively
for Intel platforms so the tricks I like to play with pointer
math may not work on any other platform.
Nick.
- Raw text -