1

考虑以下居中的六边形位板表示（填充以粗体显示）：

                56
            55      49
        54      48      42
    53      47      41      35
52      46      40      34      28
    45      39      33      27
44      38      32      26      20
    37      31      25      19
36      30      24      18      12
    29      23      17      11
28      22      16      10      04
    21      15      09      03
20      14      08      02      60
    13      07      01      59
        06      00      58
            63      57
                56

此表示适合 64 位整数，并允许通过分别向右或向左旋转位 1、7 或 8 个空格，在 6 个六边形方向上轻松移动。如果它有助于可视化，您可以将此六边形变形为正方形：

42  43  44  45  46  47  48

35  36  37  38  39  40  41

28  29  30  31  32  33  34

21  22  23  24  25  26  27

14  15  16  17  18  19  20

07  08  09  10  11  12  13

00  01  02  03  04  05  06

现在，我想做的是顺时针旋转这个位板 60°，这样 [45,46,47,38,39,31] 三角形变成 [48,41,34,40,33,32] 三角形等。 我该怎么做呢？

4

1 回答 1

3

这种排列有点混乱，每个相关的位都有不同的移动距离。排列图如下所示（最上面一行是输出）：

烫发图

不过，这确实提出了一些方法。如果我们看靠近顶部，每个“组”都是通过从输入中按升序收集一些位来形成的，因此可以通过 7 次compress_right操作来完成，PEXT这在 Intel 上是有效的（目前在 AMD 上效率不高）。真正归结为对垂直列进行采样，因此以 8 的步幅提取位。

因此，如果PEXT可以接受，可以这样做（未经测试）：

uint64_t g0 = _pext_u64(in, 0x8080808);
uint64_t g1 = _pext_u64(in, 0x404040404);
uint64_t g2 = _pext_u64(in, 0x20202020202);
uint64_t g3 = _pext_u64(in, 0x1010101010101);
uint64_t g4 = _pext_u64(in, 0x808080808080);
uint64_t g5 = _pext_u64(in, 0x404040404000);
uint64_t g6 = _pext_u64(in, 0x202020200000);
uint64_t out = g0 |  (g1 << 7) |  (g2 << 14) | (g3 << 21) |
               (g4 << 28) | (g5 << 35) | (g6 << 42);

这种排列不能被蝴蝶网络路由，但 Beneš 网络是通用的，因此可以工作。

因此，可以通过以下11 个置换步骤来完成，也称为增量交换：

word bit_permute_step(word source, word mask, int shift) {
  word t;
  t = ((source >> shift) ^ source) & mask;
  return (source ^ t) ^ (t << shift);
  }

在如何创建精确的蒙版方面有一些选择，但这有效：

x = bit_permute_step(x, 0x1001400550054005, 1);
x = bit_permute_step(x, 0x2213223111023221, 2);
x = bit_permute_step(x, 0x01010B020104090E, 4);
x = bit_permute_step(x, 0x002900C400A7007B, 8);
x = bit_permute_step(x, 0x00000A0400002691, 16);
x = bit_permute_step(x, 0x0000000040203CAD, 32);
x = bit_permute_step(x, 0x0000530800001CE0, 16);
x = bit_permute_step(x, 0x000C001400250009, 8);
x = bit_permute_step(x, 0x0C00010403080104, 4);
x = bit_permute_step(x, 0x2012000011100100, 2);
x = bit_permute_step(x, 0x0141040000000010, 1);
于 2018-09-01T23:02:41.170 回答