Bit Manipulation Problem

This post is a bit different from my usual content. It's not about Haskell or functional programming, and not strictly about software. But I think it's a nice little brain teaser that may be of interest. Some may view it as too much tedium (congruent to 3 or 4 mod 5 in Knuth's scoring system), but I found the multitude of beautiful patterns in this problem interesting enough that I didn't notice the tedium.

Consider a chessboard with squares numbered as follows (in octal):

8|  70 71 72 73 74 75 76 77
7|  60 61 62 63 64 65 66 67
6|  50 51 52 53 54 55 56 57
5|  40 41 42 43 44 45 46 47
4|  30 31 32 33 34 35 36 37
3|  20 21 22 23 24 25 26 27
2|  10 11 12 13 14 15 16 17
1|  00 01 02 03 04 05 06 07
     a  b  c  d  e  f  g  h

This is a natural 0-63 (decimal) numbering where the 3 high bits (first octal digit) of the position index indicate the row and the 3 low bits (second octal digit) indicate the column. This isn't the only way the chessboard can be enumerated. Consider the following numbering scheme (also in octal):

8|  64 04 14 24 26 16 06 66
7|  05 65 34 44 46 36 67 07
6|  15 35 74 54 56 76 37 17
5|  25 45 55 75 77 57 47 27
4|  21 41 51 71 73 53 43 23
3|  11 31 70 50 52 72 33 13
2|  01 61 30 40 42 32 63 03
1|  60 00 10 20 22 12 02 62
     a  b  c  d  e  f  g  h

You might want to take a moment to analyze the patterns in this numbering. They're very interesting.

The bottom line is that the location of a piece can be described using 6 bits and some known numbering system. Therefore, all possible locations of one piece are equivalent to all 6 bit numbers. All possible arrangements of two pieces can be enumerated with a 12 bit number, 6 bits for the location of each piece. (Note that this representation includes positions where two pieces are on the same square, but we won't worry about that for the purpose of this problem.) And of course this can be extended to more pieces very easily. But instead of just storing 6 bits of one piece and then 6 bits of the other, it's useful to put the 3 high bits of each piece together and the 3 low bits together.

To illustrate, let's assume that our piece list is an array {rook, king} and their positions are another array {052, 046} (octal. I'll use the C notation of starting with a leading zero to denote octal from now on.).

Our index for this position will be the 12 bit number 04562. To make it very clear, the ordering here is: piece 1 high bits, piece 0 high bits, piece 1 low bits, piece 0 low bits. The nice thing about having this index all in one number is that you can do operations on all the piece positions at the same time rather than looping through an array handling each piece location individually.

It is useful to be able to flip the board in different directions. When there are no pawns, there are 3 ways to flip the board that do not change the meaning of the position. You can flip around the horizontal, vertical, and diagonal axes. If you are using the first square numbering, you can flip a single piece position around the horizontal axis by calculating highBits XOR 7. You can flip around the vertical axis by calculating lowBits XOR 7. And you can flip around the diagonal axis by swapping the high bits and low bits. But that's for a single piece. For an n-piece endgame position index with the high and low bits together as described above, the following C code will do it.

const uint numBits = 3*numPieces;
const u64 lowBits = ((1ULL << numBits)-1);
const u64 highBits = lowBits << numBits;

// Flip around horizontal axis
flippedIndex = index ^ lowBits;

// Flip around vertical axis
flippedIndex = index ^ highBits;

// Flip around diagonal axis
flippedIndex = ((index&highBits) >> numBits) | ((index&lowBits) << numBits);

Again, this code works for the first square numbering. The puzzle is to write code that does these flips for the second square numbering. Now the easy way would be to create three tables of 64 values each that you can use to look up the flipped squares. But in order to use that, you'd have to loop through each piece, extract the piece's location from the index, lookup that square in the table, and store the flipped square into the correct bits of the new index. Looping through the pieces is slow. How can you do it without having to loop through the pieces?