Since mathfunners have impressed me with their crazy-bit-twiddling capabilities, here's a challenge. In chess programming, they often employ 8x8 "bitboards" -- i.e. 64-bit machine words. A bitboard question which I think has never been fully answered, is this. There are 8 ways, given a 8x8 chessboard, to rotate and flip it (dihedral group D4). For each of the 7 non-identity ways, find the fastest algorithm you can that performs that bit-permutation on a 64-bit word. Henry Warren's book "Hacker's delight" already discussed the 8x8 matrix transpose, which is one of these 7 problems. He ended up with the following incredible algorithm: uint64 TransposeBitBd(BitBd x){ //Adapted from Warren:: Hacker's delight. uint64 t; t = (x ^ (x >> 7)) & U64(0x00AA00AA00AA00AA); x = x ^ t ^ (t << 7); t = (x ^ (x >> 14)) & U64(0x0000CCCC0000CCCC); x = x ^ t ^ (t << 14); t = (x ^ (x >> 28)) & U64(0x00000000F0F0F0F0); x = x ^ t ^ (t << 28); return(x); } Good luck figuring it out. Another pointed out by Jorg Arndt is: the single machine instruction "bswap" (on many processors) is available which permutes the 8 bytes into reverse order -- this causes the board to flip vertically (or horizontally, depending how you'd ordered its bits in a raster). Another (180 degree board rotate) is the bit-reversal permutation, for which an extremely fast and mysterious algorithm is given by Don Knuth and you can go even faster on machines with bswap, we discussed this problem in earlier posts. For 90 and 270 degree board rotations with or without accompanying flips, I can do it in O(N) operations on an NxN bitboard in various fairly obvious ways that involve multiplications and maskings. Is it possible to achieve o(N) somehow? If the squares of the board were numbered 0..63 in a peculiar manner, e.g. the top left quadrant is numbered 0..15 then the other quadrants are numbered 16..31, 32..47, 48..63 in symmetric (rotated) ways, then you could perform a 90, 180, or 270 degree rotation trivially by simply doing a single circular-shift-by-16 (32, 48) hops on the 64-bit word. Probably this strange kind of numbering would be unfriendly for most computer chess purposes (?), but for this purpose it's great. More precisely, I believe there is an ordering of the 64 chessboard squares 0..63 (and there are sub-orderings of the 4x4 board 0..15 and 2x2 board 0..3) with these properties: 90 rotate: add 16 mod 64, aka circular shift by 16 180 rotate: add 32 mod 64 270 rotate: subtract 16 mod 64 For the 4x4: 90 rotate: add 4 mod 16, aka circular shift by 4 180 rotate: add 8 mod 16 270 rotate: subtract 4 mod 16 For the 2x2 where the ordering is 32 01: 90 rotate: add 1 mod 4, aka circular shift by 1 180 rotate: add 2 mod 4 270 rotate: subtract 1 mod 4 flip horizontally: XOR with 01 flip vertically: XOR with 11 And back on the full 8x8: flip board: permute the four 16-bit subwords as ABCD -> BADC or ABCD -> CDAB, and then within each 16-bit subword, perform a 4x4 flip. This in turn is accomplished recursively by the same operation on its four 4-bit subwords, then within each do a 2x2 flip as described above. So, my head is hurting, but it seems as though by means of this kind of numbering scheme, it becomes possible on an NxN bitboard (N=power of 2) to implement the 4 rotation operations in O(1) steps each, and the flip operation in O(logN) steps. I'll only believe the latter when I see more details, so for now regard this as a sketch/conjecture. It might be you cannot "parallelize" it and hence cannot achieve logN, instead getting something sadder like N or sqrt(N) steps. Anyhow, the original dihedral-7 problem is clearly not a triviality. -- Warren D. Smith http://RangeVoting.org