Subj : Re: parity checksum algorithm
To   : comp.programming
From : Alex Fraser
Date : Wed Oct 05 2005 11:16 am

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

I don't know. It would not surprise me if many people came up with it
independently.

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

The above works for (up to) 32-bit values (and, as a sidenote, assumes type
unsigned is larger than 16-bit, which isn't guaranteed). Adding more steps
would allow it to work for larger values, and removing them would restrict
it to smaller ones.

If the bits are numbered from 0 (LSB) to 31 (MSB), then the first step (a ^=
a >> 16) makes each bit n, 0 <= n < 16, the even parity of bits n and n+16
in the original value.

The next step (a ^= a >> 8) makes each bit n, 0 <= n < 8, the even parity of
bits n, n+8, n+16 and n+24 of the original value.

The third step (a ^= a >> 4) makes each bit n, 0 <= n < 4, the even parity
of bits n, n+4, n+8, ... n+28 of the original value.

And so on, ultimately leaving bit 0 as the even parity of bits 0 to 31 of
the original value.

Alex

.