Author: Gerd Isenberg
Date: 02:29:38 06/24/04
Go up one level in this thread
On June 23, 2004 at 17:14:41, Gerd Isenberg wrote:
>Hi all,
>
>first, congrats to Netherlands and Czechia!
>Condolences to Germany ;-( and the very unlucky Italy.
>
>I played a bit with parity words and for some reason thought about a inverse
>function. The solution was new to me and surprisingly simple. Imagine following
>mod2 or bitwise matrix operation to build a 32-bit parity word (or is there any
>other term for that?):
>
>x0 = x0
>x1 = x1 ^ x0
>x2 = x2 ^ x1 ^ x0
>x3 = x3 ^ x2 ^ x1 ^ x0
>......
>x31 = x31 ^ x30 ^...^ x3 ^ x2 ^ x1 ^ x0
>
>It may be computed parallel prefix wise with five "xor" and "shift"
>instructions:
>
> x ^= x<<1;
> x ^= x<<2;
> x ^= x<<4;
> x ^= x<<8;
> x ^= x<<16;
>
>Some bit(i) of the parity word indicates whether there is an odd or even number
>of ones from bit i (including) until the least significant bit, zero.
>
>"Surprisingly" one additional
>
> x ^= x<<1;
>
>is the inverse function of the above instruction sequence and restores the
>initial x. A circle - 64-bit words require one additional x ^= x<<32.
>
Similar is possible with the gray-code conversion:
http://aggregate.org/MAGIC/#Gray Code Conversion
x ^= x >> 16;
x ^= x >> 8;
x ^= x >> 4;
x ^= x >> 2;
x ^= x >> 1;
here one additional
x ^= x >> 1;
is the inverse function and restores the initial value too.
Gerd
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.