Flip 4x4 bit-grid horizontally/vertically/diagonally

Question

I am programming a board game with ab board of 4x4 squares and use a unsigned short to save whether a stone is on each square. 0 := empty square and 1 := stone on square

A board with 8 stones like this:

is saved line by line like this:

unsigned short board = 0b1111000001011010 // = 61530

I need to flip the board vertically,horizontally and diagonally.

Example:

Vertically	Horizontally	Diagonally
1010 0101 0000 1111	1111 0000 1010 0101	1001 1010 1001 1010
`0b1010010100001111 //= 42255`	`0b1111000010100101 //= 61605`	`0b1001101010011010 //= 39578`

What is the best way to do each of these three operations in c++

I thought about a lookup table but there must be a better more elegant solution.

Take a look at the [bitwise operators](https://en.cppreference.com/w/cpp/language/operator_arithmetic). — Ted Lyngmo, Jan 07 '21 at 12:23
https://stackoverflow.com/questions/25750844/how-can-i-shuffle-bits-efficiently has some approaches that might interest you. — Thomas, Jan 07 '21 at 12:27
Possible duplicate https://stackoverflow.com/questions/43575633/fast-bit-permutation — n. m. could be an AI, Jan 07 '21 at 12:28

score 1 · Accepted Answer · answered Jan 07 '21 at 12:57

All three operations can be expressed using bitwise operations like this:

uint16_t vert_flip_board(uint16_t x) {
    return ((x & 0b0000'0000'0000'1111) << 12) |
           ((x & 0b0000'0000'1111'0000) <<  4) |
           ((x & 0b0000'1111'0000'0000) >>  4) |
           ((x & 0b1111'0000'0000'0000) >> 12);
}

uint16_t horiz_flip_board(uint16_t x) {
    return ((x & 0b0001'0001'0001'0001) << 3) |
           ((x & 0b0010'0010'0010'0010) << 1) |
           ((x & 0b0100'0100'0100'0100) >> 1) |
           ((x & 0b1000'1000'1000'1000) >> 3);
}

uint16_t transpose_board(uint16_t x) {
    return  // Main diagonal.
            (x & 0b1000'0100'0010'0001) |
           // Upper diagonals.
           ((x & 0b0100'0010'0001'0000) >> 3) |
           ((x & 0b0010'0001'0000'0000) >> 6) |
           ((x & 0b0001'0000'0000'0000) >> 9) |
           // Lower diagonals.
           ((x & 0b0000'1000'0100'0010) << 3) |
           ((x & 0b0000'0000'1000'0100) << 6) |
           ((x & 0b0000'0000'0000'1000) << 9);
}

StureS · Answer 2 · 2021-01-10T09:21:27.400

A general function for bit swapping which you can use:

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Swap bits in an integer number
// pos1, pos2 are the start positions (= the bit numbers) from the right to the left in theNumber where the bits 
// should be interchanged.
// shiftcount is the number of bits that will be affected
//
// Original code: https://www.geeksforgeeks.org/swap-bits-in-a-given-number/
//
template <typename iint>
iint SwapBits(iint theNumber, unsigned int pos1, unsigned int pos2, unsigned int shiftCount)
{
    iint bitMask = ((iint)1 << shiftCount) - 1; // Create the AND bitmask
    iint set1 = (theNumber >> pos1) & bitMask;  // Move all bits of first set to rightmost side 
    iint set2 = (theNumber >> pos2) & bitMask;  // Do the same with the second
    iint exor = (set1 ^ set2);                  // XOR the two sets
    exor = (exor << pos1) | (exor << pos2);     // Put the xor'ed bits back to their original positions 
    iint result = theNumber ^ exor;             // XOR the 'exor' with the original number so that the two sets are swapped
    return result;
}

For debug purposes you can use this function to print numbers in binary:

//////////////////////////////////////////////////////////////////////////////////////////////
// Function to get a binary representation of an integer number as a string for printf
//
// Use it like this:
// short num = 0x8008; // You can use (unsigned) char, short, int, int64_t etc.
// printf("%s\n", NumToBinary(num)); // Prints 1000000000001000
//
template <typename num>
char *NumToBinary(num theNumber, char *binBuf = NULL)
{
    static char asBinary[9];    // Max int64 plus terminating zero
    int i;
    char *p = asBinary;                             // Buffer pointer

    if (binBuf)                                     // User supplied buffer present
        p = binBuf;                                 // Use it instead of the static buffer
    int bitLen = sizeof(num) << 3;                  // Number of bits in theNumber, 2^3 = 8
    uint64_t bit = (uint64_t)0x1 << (bitLen - 1);   // Start with MSB
    for (i = 0; i < bitLen; i++)
    {
        p[i] = ((theNumber & bit) == bit) ? '1' : '0';
        bit >>= 1;
    }
    p[i] = '\0';
    return p;
}

Flip 4x4 bit-grid horizontally/vertically/diagonally

I need to flip the board vertically,horizontally and diagonally.

2 Answers2