Skip to main content
6 of 8
deleted 40 characters in body
Zacariaz
  • 383
  • 2
  • 10

Rotating 3D bit board in C

I've got a 64 bit bitboard, but instead of interpreting as an 8 by 8 binary matrix, as is usually the case, I've taken it to the third dimension, so to speak.

Now mirroring and even rotating by 180 degrees on any individual axis is, if I'm not mistaken, fairly simple, but rotating by 90 degrees, which is what I actually need, has given me a nasty headache.

I have of course come up with a solution, but I would like to ensure that there isn't a better way, because frankly it's a bit much.

Anyway, here an example function, rotating, I suppose, clockwise on the Y axis:

uint64_t rotateLeft( uint64_t bs )
{
     return ( ( bs & 0x0000000000001111 ) << 48 ) |
            ( ( bs & 0x0000000000002222 ) << 31 ) |
            ( ( bs & 0x0000000000004444 ) << 14 ) |
            ( ( bs & 0x0000000000008888 ) >>  3 ) |
            ( ( bs & 0x0000000011110000 ) << 33 ) |
            ( ( bs & 0x0000000022220000 ) << 16 ) |
            ( ( bs & 0x0000000044440000 ) >>  1 ) |
            ( ( bs & 0x0000000088880000 ) >> 18 ) |
            ( ( bs & 0x0000111100000000 ) << 18 ) |
            ( ( bs & 0x0000222200000000 ) <<  1 ) |
            ( ( bs & 0x0000444400000000 ) >> 16 ) |
            ( ( bs & 0x0000888800000000 ) >> 33 ) |
            ( ( bs & 0x1111000000000000 ) <<  3 ) |
            ( ( bs & 0x2222000000000000 ) >> 14 ) |
            ( ( bs & 0x4444000000000000 ) >> 31 ) |
            ( ( bs & 0x8888000000000000 ) >> 48 );
}

I suppose 16 shifts, 16 ANDs and 15 ORs is not actually that bad, but I cannot believe that this is the best option.

So is there another/better way? I need both direction for the X and Y axis, but I suppose the solution will be somewhat similar for all of them, assuming of course that there is a better way.

Come to think of it you could do something like:

uint64_t rotateLeft( uint64_t bs )
{
    //mirror in diagonal plane (x=z?)
    bs =   ( ( bs & 0x0000000000008888 ) << 45 ) | ( ( bs & 0x1111000000000000 ) >> 45 ) |
           ( ( bs & 0x0000000088884444 ) << 30 ) | ( ( bs & 0x2222111100000000 ) >> 30 ) |
           ( ( bs & 0x0000888844442222 ) << 15 ) | ( ( bs & 0x4444222211110000 ) >> 15 ) |
             ( bs & 0x8888444422221111 );
    //mirror in vertical plane (xy?)
    //I do apologize  for not knowing the correct terminology.
    bs =   ( ( bs & 0x00000000ffffffff ) << 32 ) | ( ( bs & 0xffffffff00000000 ) >> 32 );
    return ( ( bs & 0x0000ffff0000ffff ) << 16 ) | ( ( bs & 0xffff0000ffff0000 ) >> 16 ) |
}

I would even think that could be improved a bit without too much effort. Still, I'd be interested in any suggestions.

edit: I've been informed that clarification is needed, so I'll do my best. Firstly, structurally I'm talking about a 4 by 4 by 4 cube. Line 1 of layer 1 consist of bits 0 through 3 Line 2 of layer 2 of bits 20 through 23 layer 3 of bits 32 through 47 and so on. for each layer lsb is at the top left and msb is bottom right, counting line wise.

and example of rotating left could be: layer 1-4:

1000 0000 0000 0000
0100 0000 0000 0000
0010 0000 0000 0000
0001 0000 0000 0000

to

0000 0000 0000 1000
0000 0000 1000 0000
0000 1000 0000 0000
1000 0000 0000 0000

or

0x0000 0000 0000 8421

to

0x1000 0100 0010 0001

I hope this clarifies matters a bit.

edit 2: as request, here the implementation:

uint64_t board_with_exactly_one_bit_set(int x, int y, int z)
{
    return 1 << ( z*16 +y*4 +x );
}
Zacariaz
  • 383
  • 2
  • 10