From: nick AT tcp DOT co DOT uk (Nick Austin)
Newsgroups: comp.os.msdos.djgpp
Subject: Re: (none)
Date: Sat, 12 Jul 1997 19:25:31 GMT
Organization: 0%
Lines: 46
Message-ID: <5q8lnn$iq1$1@zeus.tcp.net.uk>
References: <Pine DOT SV4 DOT 3 DOT 93 DOT 970710151909 DOT 18181A-100000 AT giasbga>
NNTP-Posting-Host: du-045.tcp.co.uk
To: djgpp AT delorie DOT com
DJ-Gateway: from newsgroup comp.os.msdos.djgpp
Precedence: bulk

"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.