algorithm - 快速位置换

Question

我需要存储排列并将其应用于 16 位整数。我想出的最佳解决方案是将排列存储为 64 位整数，其中每 4 位对应于第 i 位的新位置，应用程序如下所示:

int16 permute(int16 bits, int64 perm)
{
   int16 result = 0;
   for(int i = 0; i < 16; ++i)
      result |= ((bits >> i) & 1) * (1 << int( (perm >> (i*4))&0xf ));
   return result;
}

有没有更快的方法来做到这一点？谢谢。

Answer 1

还有其他选择。

任何排列都可以由 Beneš network 处理，并编码为掩码，这些掩码是多路复用器的输入以应用混洗。这也可以在软件中相当有效地完成(不是很好但还可以)，它只是一堆蝴蝶排列。掩码的计算有点棘手，但应用起来可能比单独移动每一位更快，尽管这取决于您要处理的位数，16 个并不多。

一些较小类别的洗牌可以由更简单(更快)的网络处理，您也可以在该页面上找到它们。

最后在实践中，在现代 x86 硬件上，有高度通用的 pshufb 函数，它可以在(通常)单个周期中对 16 字节应用排列(但可能包括重复和零)。是slightly awkward在字节上分配位，但是一旦你到达那里，它只需要一个 pshufb 来置换和一个 pmovmskb 将它压缩回 16 位。