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:

unsigned long long rotateLeft( unsigned long long bs )
{
     return ( ( bs &amp; 0x0000000000001111 ) &lt;&lt; 48 ) |
            ( ( bs &amp; 0x0000000000002222 ) &lt;&lt; 31 ) |
            ( ( bs &amp; 0x0000000000004444 ) &lt;&lt; 14 ) |
            ( ( bs &amp; 0x0000000000008888 ) &gt;&gt;  3 ) |
            ( ( bs &amp; 0x0000000011110000 ) &lt;&lt; 33 ) |
            ( ( bs &amp; 0x0000000022220000 ) &lt;&lt; 16 ) |
            ( ( bs &amp; 0x0000000044440000 ) &gt;&gt;  1 ) |
            ( ( bs &amp; 0x0000000088880000 ) &gt;&gt; 18 ) |
            ( ( bs &amp; 0x0000111100000000 ) &lt;&lt; 18 ) |
            ( ( bs &amp; 0x0000222200000000 ) &lt;&lt;  1 ) |
            ( ( bs &amp; 0x0000444400000000 ) &gt;&gt; 16 ) |
            ( ( bs &amp; 0x0000888800000000 ) &gt;&gt; 33 ) |
            ( ( bs &amp; 0x1111000000000000 ) &lt;&lt;  3 ) |
            ( ( bs &amp; 0x2222000000000000 ) &gt;&gt; 14 ) |
            ( ( bs &amp; 0x4444000000000000 ) &gt;&gt; 31 ) |
            ( ( bs &amp; 0x8888000000000000 ) &gt;&gt; 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:

unsigned long long rotateLeft( unsigned long long bs )
{
    //mirror in diagonal plane (x=z?)
    bs =   ( ( bs &amp; 0x0000000000008888 ) &lt;&lt; 45 ) | ( ( bs &amp; 0x1111000000000000 ) &gt;&gt; 45 ) |
           ( ( bs &amp; 0x0000000088884444 ) &lt;&lt; 30 ) | ( ( bs &amp; 0x2222111100000000 ) &gt;&gt; 30 ) |
           ( ( bs &amp; 0x0000888844442222 ) &lt;&lt; 15 ) | ( ( bs &amp; 0x4444222211110000 ) &gt;&gt; 15 ) |
             ( bs &amp; 0x8888444422221111 );
    //mirror in vertical plane (xy?)
    //I do apologize  for not knowing the correct terminology.
    bs =   ( ( bs &amp; 0x00000000ffffffff ) &lt;&lt; 32 ) | ( ( bs &amp; 0xffffffff00000000 ) &gt;&gt; 32 );
    return ( ( bs &amp; 0x0000ffff0000ffff ) &lt;&lt; 16 ) | ( ( bs &amp; 0xffff0000ffff0000 ) &gt;&gt; 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 &lt;&lt; ( z*16 +y*4 +x );
}
First of all, it might help to explain the problem domain; you might have an XY problem here. The first application for "4x4x4 bitboards" that pops into my head is that you're dealing with Rubik's Revenge... but representing cubelets by single bits is not of obvious utility to me, and rotating the entire cube by 90 degrees is even less useful.

Next, this does seem like the sort of thing that has a known solution somewhere, so I'd definitely recommend doing a thorough Google search. (Asking StackOverflow might also be appropriate; but that's just offloading the Google search onto somebody else. It would be polite to do some searching yourself first, and report the results.) I didn't do any searching myself other than a quick fruitless skim through HAKMEM; but if you find out "the" answer, I'd be mildly interested to hear about it.

Okay, so, let's assume that we've got a 4x4x4 bitboard that looks like this:

uint64_t board_with_one_bit_set(int x, int y, int z)
{
    int index = (x + 4*y + 16*z);
    return 1uLL &lt;&lt; index;
}


Notice that "rotating a bitboard" is a special case of "permuting the bits in a word." That is, we expect our result to have the same parity as the input — and in fact the same bits, just in a different order. So mathematically it might make more sense to think of this as a permutation of a 64-element sequence, rather than as a bunch of imperative shifts and masks.

To avoid brain farts, I decided to write a little Python script to generate the bit-shifting code from the permutation. Here's the input:

original = [
    63, 62, 61, 60,
    59, 58, 57, 56,
    55, 54, 53, 52,
    51, 50, 49, 48,
                   47, 46, 45, 44,
                   43, 42, 41, 40,
                   39, 38, 37, 36,
                   35, 34, 33, 32,
                                  31, 30, 29, 28,
                                  27, 26, 25, 24,
                                  23, 22, 21, 20,
                                  19, 18, 17, 16,
                                                 15, 14, 13, 12,
                                                 11, 10, 9,  8,
                                                 7,  6,  5,  4,
                                                 3,  2,  1,  0,
]
rotated_right_around_x_axis = [
    51, 50, 49, 48,
    35, 34, 33, 32,
    19, 18, 17, 16,
    3,  2,  1,  0,
                   55, 54, 53, 52,
                   39, 38, 37, 36,
                   23, 22, 21, 20,
                   7,  6,  5,  4,
                                  59, 58, 57, 56,
                                  43, 42, 41, 40,
                                  27, 26, 25, 24,
                                  11, 10, 9,  8,
                                                 63, 62, 61, 60,
                                                 47, 46, 45, 44,
                                                 31, 30, 29, 28,
                                                 15, 14, 13, 12,
]


(I think this is right. "Rotating right around the x axis" means pointing your right thumb in the direction of increasing x, which I think of as "to the left", and curling your fingers in the direction of the rotation, which I think of as "top-moves-away". However, even with this much effort to avoid brain farts, I might have messed it up.)

Here's the Python code for converting the input into a C++ function body:

def to_cpp11_hex(mask):
    return "0x%04X'%04X'%04X'%04X" % (
        ((mask &gt;&gt; 48) &amp; 0xFFFF),
        ((mask &gt;&gt; 32) &amp; 0xFFFF),
        ((mask &gt;&gt; 16) &amp; 0xFFFF),
        ((mask &gt;&gt; 0) &amp; 0xFFFF),
    )

def print_function_body(original, rotated):
    bits_by_rotation = {}
    for b in xrange(64):
        o = original.index(b)
        r = rotated.index(b)
        rotl_amount = ((o - r) + 64) % 64
        bits_by_rotation.setdefault(rotl_amount, []).append(r)
    print '    uint64_t r = 0;'
    for amount, bits in sorted(bits_by_rotation.iteritems()):
        mask = sum(1 &lt;&lt; b for b in bits)
        print '    r |= rotl(o, %d) &amp; %s;' % (amount, to_cpp11_hex(mask))
    print '    return r;'

print_function_body(original, rotated_right_around_x_axis)


This script generates functions like the following:

inline constexpr uint64_t rotl(uint64_t x, int k)
{
    return (x &lt;&lt; k) | (x &gt;&gt; (64-k));
}

uint64_t rotate_left_around_x_axis(uint64_t o)
{
    uint64_t r = 0;
    r |= rotl(o, 4) &amp; 0x0000'00F0'0000'0000;
    r |= rotl(o, 8) &amp; 0x0000'0000'0000'0F00;
    r |= rotl(o, 12) &amp; 0x000F'0000'0000'0000;
    r |= rotl(o, 16) &amp; 0xF000'0000'00F0'0000;
    r |= rotl(o, 24) &amp; 0x0000'000F'0000'0000;
    r |= rotl(o, 28) &amp; 0x0000'F000'0000'00F0;
    r |= rotl(o, 36) &amp; 0x0F00'0000'000F'0000;
    r |= rotl(o, 40) &amp; 0x0000'0000'F000'0000;
    r |= rotl(o, 48) &amp; 0x0000'0F00'0000'000F;
    r |= rotl(o, 52) &amp; 0x0000'0000'0000'F000;
    r |= rotl(o, 56) &amp; 0x00F0'0000'0000'0000;
    r |= rotl(o, 60) &amp; 0x0000'0000'0F00'0000;
    return r;
}

uint64_t rotate_right_around_x_axis(uint64_t o)
{
    uint64_t r = 0;
    r |= rotl(o, 4) &amp; 0x0000'0000'00F0'0000;
    r |= rotl(o, 8) &amp; 0x0000'F000'0000'0000;
    r |= rotl(o, 12) &amp; 0x0000'0000'0000'000F;
    r |= rotl(o, 16) &amp; 0x000F'0000'0F00'0000;
    r |= rotl(o, 24) &amp; 0x0000'0000'0000'00F0;
    r |= rotl(o, 28) &amp; 0x00F0'0000'F000'0000;
    r |= rotl(o, 36) &amp; 0x0000'000F'0000'0F00;
    r |= rotl(o, 40) &amp; 0x0F00'0000'0000'0000;
    r |= rotl(o, 48) &amp; 0x0000'00F0'0000'F000;
    r |= rotl(o, 52) &amp; 0xF000'0000'0000'0000;
    r |= rotl(o, 56) &amp; 0x0000'0000'000F'0000;
    r |= rotl(o, 60) &amp; 0x0000'0F00'0000'0000;
    return r;
}


I don't immediately see any improvements. I had various ideas, such as trying to incrementally rotate o by repetitions of

    r |= (o = rotl(o, 4-or-8)) &amp; MASK;


or limiting all the masks to 32 bits for x86-64-friendliness

def print_function_body_32bit(original, rotated):
    bits_by_rotation = {}
    for b in xrange(32, 64):
        o = original.index(b)
        r = rotated.index(b)
        rotl_amount = ((o - r) + 64) % 64
        bits_by_rotation.setdefault(rotl_amount, []).append(r)
    print '    uint64_t r = 0;'
    for amount, bits in sorted(bits_by_rotation.iteritems()):
        mask = sum(1 &lt;&lt; b for b in bits)
        print '    r |= rotl(o, %d) &amp; %s;' % ((amount + 32) % 64, to_cpp11_hex((mask &gt;&gt; 32) &amp; 0xFFFFFFFF))
    print '    r &lt;&lt;= 32;'
    bits_by_rotation = {}
    for b in xrange(0, 32):
        o = original.index(b)
        r = rotated.index(b)
        rotl_amount = ((o - r) + 64) % 64
        bits_by_rotation.setdefault(rotl_amount, []).append(r)
    for amount, bits in sorted(bits_by_rotation.iteritems()):
        mask = sum(1 &lt;&lt; b for b in bits)
        print '    r |= rotl(o, %d) &amp; %s;' % (amount, to_cpp11_hex(mask &amp; 0xFFFFFFFF))
    print '    return r;'


which generates function bodies like

uint64_t rotate_right_around_x_axis(uint64_t o)
{
    uint64_t r = 0;
    r |= rotl(o, 36) &amp; 0x0000'0000'0000'0000;
    r |= rotl(o, 44) &amp; 0x0000'0000'0000'0000;
    r |= rotl(o, 48) &amp; 0x0000'0000'000F'0000;
    r |= rotl(o, 56) &amp; 0x0000'0000'0000'0000;
    r |= rotl(o, 60) &amp; 0x0000'0000'00F0'0000;
    r |= rotl(o, 4) &amp; 0x0000'0000'0000'000F;
    r |= rotl(o, 16) &amp; 0x0000'0000'0000'00F0;
    r |= rotl(o, 24) &amp; 0x0000'0000'0000'0000;
    r &lt;&lt;= 32;
    r |= rotl(o, 8) &amp; 0x0000'0000'0000'0000;
    r |= rotl(o, 16) &amp; 0x0000'0000'0F00'0000;
    r |= rotl(o, 28) &amp; 0x0000'0000'F000'0000;
    r |= rotl(o, 36) &amp; 0x0000'0000'0000'0F00;
    r |= rotl(o, 40) &amp; 0x0000'0000'0000'0000;
    r |= rotl(o, 48) &amp; 0x0000'0000'0000'F000;
    r |= rotl(o, 52) &amp; 0x0000'0000'0000'0000;
    r |= rotl(o, 60) &amp; 0x0000'0000'0000'0000;
    return r;
}


which are nevertheless longer (in terms of number of assembly instructions) than the more "naïve" 64-bit version.

Writing an appropriate benchmark for the various possibilities, and writing out the permutation matrices for rotated_right_around_y_axis and rotated_right_around_z_axis, are left as exercises for the interested reader.

It would also be supremely interesting to feed these "rotation-permutation" functions to a superoptimizer and see what it produces. However, my wild-ass guess is that the optimal instruction sequence is in excess of 40 instructions, which would (I think) make it intractable for the current state-of-the-art in superoptimizers. But I could be wrong. Anyway, if you find out, it would be interesting to post the results here.