文章/答案/技术大牛

发布

社区首页 >问答首页 >旋转和反射5x5位板

问旋转和反射5x5位板
EN

Stack Overflow用户

提问于 2022-05-03 09:48:05

回答 1查看 89关注 0票数 0

我试图找到一种快速的方式旋转和反射一个5x5板，以存储在一个转位表。板被表示为一个比特板，因为他们是非常快。

比特板的表示方式如下：

 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位旋转找到了一些解决方案，但是我找不到适用于5x5位板的解决方案，我也尝试过遍历所有比特并切换它们，但这是一个非常慢的解决方案。(C++)

bit-manipulation

bit

bit-shift

bitboard

bitmap

回答 1

Stack Overflow用户

回答已采纳

发布于 2022-05-04 18:06:42

转置可以用4个增量交换来完成，它的分解不如8x8转置，因为5不是2的幂。4 delta交换将花费大约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是熟悉的增量交换。

另一种方法是使用乘法提取列。例如，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使这个更好/更简单：(没有测试)

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);

水平或垂直翻转将很容易与位组移动。

票数 1

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/72097570

复制

相似问题

问旋转和反射5x5位板
EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问旋转和反射5x5位板EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问旋转和反射5x5位板
EN