1

对于我正在编写的解谜器，我正在寻找最快的算法（最少的位操作数）来转置拼图中每平方 2 位的 5x5 位板，因此：

00 01 02 03 04
05 06 07 08 09
10 11 12 13 14
15 16 17 18 19
20 21 22 23 24

变成

00 05 10 15 20
01 06 11 16 21
02 07 12 17 22
03 08 13 18 23
04 09 14 19 24

我能想到的最好的是

uint64_t transpose(uint64_t state) {
    return ((state >> 16) &     0x10) |
           ((state >> 12) &    0x208) |
           ((state >>  8) &   0x4104) |
           ((state >>  4) &  0x82082) |
           ((state <<  4) & 0x820820) |
           ((state <<  8) & 0x410400) |
           ((state << 12) & 0x208000) |
           ((state << 16) & 0x100000);
}

但感觉这可以通过显着减少的操作来完成。有谁知道更快的解决方案？也非常欢迎参考有关该主题的优秀文献。

4

1 回答 1

1

此处发现的 2048 AI具有用于 4 位图块的 4x4 网格的转置方法。也许您可以根据自己的情况进行调整。这是代码：

// Transpose rows/columns in a board:
//   0123       048c
//   4567  -->  159d
//   89ab       26ae
//   cdef       37bf
uint64_t transpose(uint64_t x)
{
    uint64_t a1 = x & 0xF0F00F0FF0F00F0FULL;
    uint64_t a2 = x & 0x0000F0F00000F0F0ULL;
    uint64_t a3 = x & 0x0F0F00000F0F0000ULL;
    uint64_t a = a1 | (a2 << 12) | (a3 >> 12);
    uint64_t b1 = a & 0xFF00FF0000FF00FFULL;
    uint64_t b2 = a & 0x00FF00FF00000000ULL;
    uint64_t b3 = a & 0x00000000FF00FF00ULL;
    return b1 | (b2 >> 24) | (b3 << 24);
}
于 2016-05-22T22:08:08.757 回答