[math-fun] reversing the order of bits in a word
WDS> 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. Smithhttp://RangeVoting.org Knuth Vol 4A, 7.1.3 has 70 pages on Bitwise Tricks and Techniques. Page 144 is Bit reversal, and may anticipate you here--I haven't read closely enough to determine. (Probably not, if Tom Karzes's "all 1s" objection resists debugging!) Certainly most of Knuth's hacks require "funny masking constants" (whose objectionability I fail to perceive). Probably the most important lesson in 7.1.3 is Knuth's strong advocacy of his MOR and MXOR (8×8 bitmatrix) instructions for inclusion in 64-bit order codes. Bit reversal takes two MORs. --rwg After Bit reversal comes Bit swapping, in which my hasty perusal fails to find the TRCE TRCE TRCE trick (HAKMEM Item 162), of which Knuth was once quite fond. It is perhaps too platform dependent? I'd think he would cite TRCE etc as ideas for future order codes, but perhaps instruction skipping is a thing of the past.
________________________________ From: Bill Gosper <billgosper@gmail.com> To: math-fun@mailman.xmission.com Sent: Friday, March 28, 2014 11:26 AM Subject: [math-fun] reversing the order of bits in a word
Probably the most important lesson in 7.1.3 is Knuth's strong advocacy of his MOR and MXOR (8×8 bitmatrix) instructions for inclusion in 64-bit order codes. Bit reversal takes two MORs. --rwg
As long as we are going to implement new instructions, better yet do a bit reverse. The MIT AI people hacked their PDP-10 to have bit reverse. Due to it's utility in FFT, I'm surprised that bit reverse is not a standard instruction.
-- Gene
I installed that instruction. It was a slight variant of the PDP-6/10 rotate combined instruction, which rotated two adjacent accumulators as a single 72 bit word. The bit reverse version shifted one accumulator right and the other left, while passing the bit across the boundary. On Mar 28, 2014, at 9:03 PM, Eugene Salamin <gene_salamin@yahoo.com> wrote:
________________________________ From: Bill Gosper <billgosper@gmail.com> To: math-fun@mailman.xmission.com Sent: Friday, March 28, 2014 11:26 AM Subject: [math-fun] reversing the order of bits in a word
Probably the most important lesson in 7.1.3 is Knuth's strong advocacy of his MOR and MXOR (8×8 bitmatrix) instructions for inclusion in 64-bit order codes. Bit reversal takes two MORs. --rwg
As long as we are going to implement new instructions, better yet do a bit reverse. The MIT AI people hacked their PDP-10 to have bit reverse. Due to it's utility in FFT, I'm surprised that bit reverse is not a standard instruction.
-- Gene
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I used the instruction. Along with multi-level indexed & indirect addressing, and an instruction that counted the number of leading 0s in a word. The program counted magic squares of size 5. The cells are filled in gradually (with about a dozen nested loops) and a bit-mask of available values is maintained. If three cells of a row are known, the sum of the unknown pair is computed. Then Anding the available-bit-mask with its (shifted) reverse gives the set of available-value pairs. Rich -------- Quoting Tom Knight <tk@mit.edu>:
I installed that instruction. It was a slight variant of the PDP-6/10 rotate combined instruction, which rotated two adjacent accumulators as a single 72 bit word. The bit reverse version shifted one accumulator right and the other left, while passing the bit across the boundary.
On Mar 28, 2014, at 9:03 PM, Eugene Salamin <gene_salamin@yahoo.com> wrote:
________________________________ From: Bill Gosper <billgosper@gmail.com> To: math-fun@mailman.xmission.com Sent: Friday, March 28, 2014 11:26 AM Subject: [math-fun] reversing the order of bits in a word
Probably the most important lesson in 7.1.3 is Knuth's strong advocacy of his MOR and MXOR (8×8 bitmatrix) instructions for inclusion in 64-bit order codes. Bit reversal takes two MORs. --rwg
As long as we are going to implement new instructions, better yet do a bit reverse. The MIT AI people hacked their PDP-10 to have bit reverse. Due to it's utility in FFT, I'm surprised that bit reverse is not a standard instruction.
-- Gene
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (4)
-
Bill Gosper -
Eugene Salamin -
rcs＠xmission.com -
Tom Knight