旋转并反射 5x5 位板

Question

我正在尝试找到一种快速旋转和反射 5x5 板以将其存储在换位中的方法 table。该板表示为位板，因为它们非常快。

位板是这样表示的：

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

我找到了一些适用于 8x8 位板的解决方案 https://www.chessprogramming.org/Flipping_Mirroring_and_Rotating 但我找不到适用于 5x5 位板的解决方案，我也尝试过遍历所有位并切换它们，但那是一个非常缓慢的解决方案。 (C++)

Answer 1

转置可以通过 4 个增量交换来完成，它不像 8x8 转置那样分解得很好，因为 5 不是 2 的幂。 4 次增量交换将花费大约 24 次操作和大约 20 个周期（由于指令级并行性，少于 24 个，但不会少于 24 个，因为代码由于依赖关系大部分是串行的）。

看起来像这样：

board = bit_permute_step(board, 0x00006300, 16);
board = bit_permute_step(board, 0x020a080a, 4);
board = bit_permute_step(board, 0x0063008c, 8);
board = bit_permute_step(board, 0x00006310, 16);

其中 bit_permute_step 是熟悉的增量掉期。

另一种方法是使用 multiplication to extract columns。例如 x & 0b0000100001000010000100001 选择一列，然后我们可以选择一个常量乘以使得该列中的位在 32 位字的前 5 位中以连续序列排列。单词的其余部分将包含这些位的其他杂散副本，但它们将被移出。例如（用C#显示，应该很容易移植）

static uint Tranpose_5x5(uint x)
{
    uint r0 = ((x & 0b0000100001000010000100001) * 0b00001000_10001000_10001000_00000000) >> 27;
    uint r1 = ((x & 0b0001000010000100001000010) * 0b00000100_01000100_01000100_00000000) >> 27;
    uint r2 = ((x & 0b0010000100001000010000100) * 0b00000010_00100010_00100010_00000000) >> 27;
    uint r3 = ((x & 0b0100001000010000100001000) * 0b00000001_00010001_00010001_00000000) >> 27;
    uint r4 = ((x & 0b1000010000100001000010000) * 0b00000000_10001000_10001000_10000000) >> 27;
    return r0 | (r1 << 5) | (r2 << 10) | (r3 << 15) | (r4 << 20);
}

在 23 次操作中，这似乎没有节省任何东西，但由于指令级并行性的机会增加，它可能具有更低的延迟。

PEXT 使得 nicer/simpler：（未测试）

int r0 = _pext_u32(board, 0b0000100001000010000100001);
int r1 = _pext_u32(board, 0b0001000010000100001000010);
int r2 = _pext_u32(board, 0b0010000100001000010000100);
int r3 = _pext_u32(board, 0b0100001000010000100001000);
int r4 = _pext_u32(board, 0b1000010000100001000010000);
return r0 | (r1 << 5) | (r2 << 10) | (r3 << 15) | (r4 << 20);

64 位 pext 可以一次提取两列，但我们必须先将板与自身连接起来，因为 pext 无法重新排序：（也未测试）

uint64_t b2 = board | (uint64_t(board) << 25);
int r01 = _pext_u64(b2, 0b0001000010000100001000010'0000100001000010000100001);
int r23 = _pext_u64(b2, 0b0100001000010000100001000'0010000100001000010000100);
int r4 = _pext_u32(board, 0b1000010000100001000010000);
return r01 | (r23 << 10) | (r4 << 20);

通过 bit-group 移动可以轻松水平或垂直翻转。

旋转并反射 5x5 位板

Rotate and reflect a 5x5 bitboard

bitmap

bit-manipulation

bit

bit-shift

bitboard