Rotating 3D bit board in C
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.