Subj : Re: parity checksum algorithm
To   : comp.programming
From : Roger Willcocks
Date : Wed Oct 05 2005 05:06 pm

"Paminu" <jadajada@asd.com> wrote in message 
news:di016i$qe0$1@news.net.uni-c.dk...
>I am interested in getting some help with the "even parity check" 
>algorithm.
> I used google to find this:
>
> unsigned parity(unsigned arg)
> {
> unsigned a = arg;
>
> a ^= a >> 16;
> a ^= a >> 8;
> a ^= a >> 4;
> a ^= a >> 2;
> a ^= a >> 1;
>
> return a & 1;
> }
>
> Who have invented this algorithm?
>
> Is it possible to find an explanation somewhere because I see that it 
> works
> but would never myself have come up with it. Therefore I would like to 
> know
> the theory behind it.

This is making use of the close relationship between 'add' and 'xor'. Xor is 
'add without carry'.

By various shifts, the code ends up adding (without carry) all the bits in 
the number and folding the result into the bottom-most bit. But since you 
only need to know whether the total number of 1's in the number is odd or 
even, you only need to look at the bottom-most bit of the result anyway, and 
the lack of carries is not a problem. Note incidentally that the five lines 
of code can be executed in any order. It may be more obvious what's going on 
if you write:

   a ^= a>>1;
   a ^= a>>2;
   a ^= a>>4;
   a ^= a>>8;
   a ^= a>>16;

The method was probably first implemented in hardware. There's a discussion 
of hardware and software implementations (including, essentially, this one) 
in the Texas Instruments design note 'parity generation on the tms320c54x' 
which you should be able to find quite easily with Google.

Compare with

int Count (unsigned int w)
{
   w = (0x55555555 & w) + (0x55555555 & (w>> 1));
   w = (0x33333333 & w) + (0x33333333 & (w>> 2));
   w = (0x0f0f0f0f & w) + (0x0f0f0f0f & (w>> 4));
   w = (0x00ff00ff & w) + (0x00ff00ff & (w>> 8));
   w = (0x0000ffff & w) + (0x0000ffff & (w>>16));
   return w;
}

which counts the number of 1's.

--
Roger

.