如何旋转居中的六角形位板？

Question

考虑以下centered hexagonal位板表示（填充以粗体显示）：

                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]三角形等。 我该怎么做呢？

Answer 1

这种排列是一种混乱，每个相关位具有不同的移动距离。排列图看起来像这样（输出顶行）：

这确实提出了一些方法。如果我们看近顶部，每个“组”都是通过从输入中按升序收集一些位来形成的，所以它可以通过7个compress_right操作来完成，这个操作也就是PEXT，它在英特尔上是有效的（到目前为止在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个these置换步骤来完成，也称为delta交换：

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