考虑以下centered hexagonal位板表示(填充以粗体显示):
<b>56</b>
<b>55</b> <b>49</b>
<b>54</b> 48 <b>42</b>
<b>53</b> 47 41 <b>35</b>
<b>52</b> 46 40 34 <b>28</b>
45 39 33 27
<b>44</b> 38 32 26 <b>20</b>
37 31 25 19
<b>36</b> 30 24 18 <b>12</b>
29 23 17 11
<b>28</b> 22 16 10 <b>04</b>
21 15 09 03
<b>20</b> 14 08 02 <b>60</b>
<b>13</b> 07 01 <b>59</b>
<b>06</b> 00 <b>58</b>
<b>63</b> <b>57</b>
<b>56</b>
此表示适合 64 位整数,并允许通过分别向右或向左旋转位 1、7 或 8 空间来在 6 个六边形方向上轻松移动。如果有助于可视化,您可以将该六边形变形为正方形:
<b>42</b> <b>43</b> <b>44</b> 45 46 47 48
<b>35</b> <b>36</b> 37 38 39 40 41
<b>28</b> 29 30 31 32 33 34
21 22 23 24 25 26 27
14 15 16 17 18 19 <b>20</b>
07 08 09 10 11 <b>12</b> <b>13</b>
00 01 02 03 <b>04</b> <b>05</b> <b>06</b>
现在,我要做的就是顺时针旋转这个位板 60°,使得 [45,46,47,38,39,31] 三角形变成 [48,41,34,40,33,32]三角形等。我该怎么做?
最佳答案
这种排列有点困惑,每个相关位都有不同的移动距离。排列图如下所示(顶行是输出):
但这确实提出了一些方法。如果我们看顶部附近,每个“组”都是通过按升序从输入中收集一些位来形成的,因此可以使用 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š 网络是通用的,因此可以工作。
所以可以用 these 中的 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);
关于algorithm - 如何旋转居中六边形位板?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/52131430/