This doesn't work. Try it will all 1's for instance. The final result ends up with lots of 0's in it. The first stage works fine, but after that some masking is needed to prevent crossover between the groups. In fact, you can easily see this by running all 1's through the final stage. With just 4 bits, you have: 1111 (initial pattern) 1000 (should be 1010) 1000 (should be 1010) 1100 (should be 1111) Tom Warren D Smith writes:
Let w be a 64-bit word ("unsigned long long," in C language). The following C instruction sequence
w ^= w>>32; w ^= w<<32; w ^= w>>32; w ^= w>>16; w ^= w<<16; w ^= w>>16; w ^= w>>8; w ^= w<<8; w ^= w>>8; w ^= w>>4; w ^= w<<4; w ^= w>>4; w ^= w>>2; w ^= w<<2; w ^= w>>2; w ^= w>>1; w ^= w<<1; w ^= w>>1;
will overwrite w with its bit-order-reversal. In general for a (2^k)-bit long word this will use 3*k shifts and 3*k XOR operations and with zero(?) or one(?) extra registers consumed for temp storage and no funny masking constants needed.
-- Warren D. Smith http://RangeVoting.org
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun