Thursday, May 14, 2009

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?

11 comments:

Alf said...

You don't need to keep the low and high bits together to be able to flip around the diagonal... you can do something like

x ^= ((x ^ (x>>3))&0707070707)*011;

Basically, as long as the sets of bits you want to swap are the same distance from eachother, you can do it with two xors. It's basically

t = a ^ b;
a ^= t;
b ^= t;

except in parallel.

mightybyte said...

The reason the low and high bits are kept together is not related to the problem of flipping the board. That index organization was chosen for reasons outside the scope of the problem as I've described it here. I just figured I'd keep the index organization the same.

That said, I'm familiar with the xor method of swapping and I like your application of it here.

winterkoninkje said...

For a single element:

To flip along the horizontal axis: \(hi,lo) -> (hi, lo `xor` 4)

To flip along the vertical axis: \(hi, lo) -> (hi, lo `xor` 2)

To flip along the diagonal: \(hi, lo) -> (hi , lo `xor` 6)

mightybyte said...

You are correct for horizontal and vertical, but not for diagonal. Your transformation achieves a 180 rotation of the board, not a flip around the diagonal axis. For clarification, I'm looking for a flip around the a1-h8 diagonal. This transformation should transform 6 into 7.

winterkoninkje said...

Right, I realized that as I was heading to bed. There's surely an easier way, but one correct answer for the diagonal is:

diag (hi,lo) = (hi, lo')
where
lo' = if (hi .|. 1) == 7
then if lo .&. 2 == shiftR (lo .&. 4) 1
then lo
else compl 6 lo .|. lo .&. 1
else shiftR (lo .&. 4) 1 .|. shiftL (lo .&. 2) 1 .|. compl 1 lo

compl mask = \x -> (x .&. mask) `xor` mask

winterkoninkje said...

Oh, of course:

diag (hi,lo) = (hi, shiftR (lo .&. 4) 1 .|. shiftL (lo .&. 2) 1 .|. (if hi > 5 then id else (`xor` 1)) (lo .&. 1))

Though I'm sure there's a better trick for swapping the bits

mightybyte said...

Your last two solutions work for a single element, but they don't fulfill my criteria of working with an index of several piece locations packed together like I describe without looping. Since you use conditionals, your solutions require looping through each individual piece in the index.

ivan said...

For a single element with the conditionals eliminated:

diag (hi,lo) = (hi, lo')
where lo' = (lo .&. 1 .|. swap lo 1 2) `xor` mul hi 1 2 `xor` 1
mul x i j = shiftR x i .&. shiftR x j .&. 1
swap x i j = shift (x .&. bit i) (j-i) .|. shift (x .&. bit j) (i-j)

I wonder if it'd be possible to extend for n elements without obfuscating the lo' definition much. Some monadic or typeclass magic maybe?

ivan said...

And a prettier version:

diag (hi, lo) = (hi, lo')
where lo' = swap lo 1 2 `xor` mul hi 1 2 `xor` 1

mul x i j = shiftR x i .&. shiftR x j .&. 1
swap x i j = x `xor` (x' .|. shift x' (i-j))
where x' = (shift x (j-i) `xor` x) .&. bit j

mightybyte said...

Nice. Now for the extension to n elements... :)

ivan said...

An easy and ugly way is to redefine the bit function:

church 0 f x = x
church n f x = church (n-1) f (f x)

pieceBits = 3
numPieces = 1

diag (hi,lo) = (hi, lo')
where lo' = swap lo 1 2 `xor` mul hi 1 2 `xor` bit 0

bit x = church numPieces (\a -> shiftL a pieceBits .|. shiftL 1 x) 0
mul x i j = shiftR x i .&. shiftR x j .&. bit 0
swap x i j = x `xor` (x' .|. shift x' (i - j))
where x' = (shift x (j - i) `xor` x) .&. bit j

I see a couple choices about where to define the bit function but they all have drawbacks.

btw, the lowBits and hightBits seem the other way around in this c example above:

// Flip around horizontal axis
flippedIndex = index ^ lowBits