Author: Matthias Gemuh
Date: 02:57:06 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. > >One application of parity words is building de Bruijn sequences N from N-1, eg. >64 from 32: > > deBruijn32: 0x04653adf > parity: 0x03dce9b5 >~parity: 0xfc23164a > insert[1]: 0x03dce9b4 1 > 1f8462c94 > deBruijn64: 0x03dce9b5f8462c95 (for that special case) > >A 32-bit de Bruijn sequence with 5 leading binary zeros and 16 ones, resets bit >32-6 due to the even parity, but sets bit 32-7 due to odd parity because 32-6 >was set before. The set bit 0 leaves unchanged. >Now a 64 bit de Bruijn sequence may be build by inserting the inverted (and >rotated) bits of the parity word somehow in the "middle" (1..27) of the parity >word, leaving six leading zeros as seen in the above example. > >Other applications? > >Cheers, >Gerd Hi Gerd, do you frequently go to outer space for some maths courses ;) ? Simply impressed as usual, Matthias.
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.