How to rotate a 64-bit BitBoard?
Hi,
I am currently programming a chess game using bitboards.
From what I have read on the internet, the best way (at least the most commonly used way) to generate moves for sliding pieces (rooks, bishops, and queens), involves the use of rotated bitboards. However, I cannot seem to come up with or find an efficient way to rotate bitboards.
For people not into chess programming, what I want to achieve is to transform something like:
Code:
11111111 00000000 00000000 00000000 00000000 00000000 00000000 00000000
to:
Code:
10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000
and:
Code:
00000001 00000001 00000001 00000001 00000001 00000001 00000001 00000001
and:
Code:
00000000 00000000 00000000 00000000 00000000 00000000 00000000 11111111
Is there any efficient way to do this?
Thank you very much.
There's another dirty trick
For all those who (like me) stumble upon this thread and can't believe there's no alternative to testing every single bit, here's a version that reduces the number of instructions a bit (at the cost of readability).
Code:
#include <stdio.h>
// gcc
typedef unsigned long long bitboard;
// msvc
//typedef unsigned __int64 bitboard;
// rotate bitboard 90° to the left
inline bitboard rotate(register bitboard b) {
register bitboard t; // temporary
// reflect b against diagonal line going through bits 1<<7 and 1<<56
t = (b ^ (b >> 63)) & 0x0000000000000001; b ^= t ^ (t << 63);
t = (b ^ (b >> 54)) & 0x0000000000000102; b ^= t ^ (t << 54);
t = (b ^ (b >> 45)) & 0x0000000000010204; b ^= t ^ (t << 45);
t = (b ^ (b >> 36)) & 0x0000000001020408; b ^= t ^ (t << 36);
t = (b ^ (b >> 27)) & 0x0000000102040810; b ^= t ^ (t << 27);
t = (b ^ (b >> 18)) & 0x0000010204081020; b ^= t ^ (t << 18);
t = (b ^ (b >> 9)) & 0x0001020408102040; b ^= t ^ (t << 9);
// reflect b against vertical center line
t = (b ^ (b >> 7)) & 0x0101010101010101; b ^= t ^ (t << 7);
t = (b ^ (b >> 5)) & 0x0202020202020202; b ^= t ^ (t << 5);
t = (b ^ (b >> 3)) & 0x0404040404040404; b ^= t ^ (t << 3);
t = (b ^ (b >> 1)) & 0x0808080808080808; b ^= t ^ (t << 1);
return b;
}
void dump(bitboard b) {
int x,y;
for (y=0; y<8; y++) {
for (x=0; x<8; x++) {
printf(b&1 ? " X" : " -");
b >>= 1;
}
printf("\n");
}
}
int main() {
bitboard test = 0x40F858187E3C1800;
dump(test);
printf("=================\n");
dump(rotate(test));
}
If you want to understand why this works, I suggest you
- Read http://www-cs-faculty.stanford.edu/~knuth/fasc1a.ps.gz, which explains why every one of the bit-twiddling lines above swaps all the bits that are set in the hex constant with those 63, 54, 45, ... positions to the left.
- Grab a piece of squared paper, mark off 8x8 squares, fill in the corresponding bit positions and convince yourself that the swappings in the two blocks do what the comments say.
- Convince yourself that the two reflections indeed are the same as the desired rotation.