快速位置换
问题描述：
我需要存储和应用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;
}
是有更快的方式做这个？谢谢。
答
还有其他选择。
任何置换均可由Beneš network处理，并作为掩码进行编码，这些掩码是多路复用器应用混洗的输入。这可以在软件中合理有效地完成（不是很好，但确定），它只是一堆蝴蝶排列。掩码的计算有点棘手，但可能比单独移动每一位更快，但这取决于你处理的位数，16位并不是很多。
一些较小类型的洗牌可以通过更简单（更快）的网络处理，您也可以在该页面上找到这些网络。
最后在实践中，在现代的x86硬件上，有一个功能非常强大的功能，可以在一个周期内（典型情况下）对16个字节应用一个置换（但可能包括伪和零）。它是slightly awkward分配字节的位，但一旦你在那里它只需要pshufb排列和pmovmskb压缩它回到16位。
如果您可以提供稍宽的上下文，它可能会有所帮助。例如，您是否需要在许多不同的位上执行相同的置换（在这种情况下，您可以准备查找表），或者按顺序多次应用相同的置换（在这种情况下，您可以使用循环分解）。 –
通常，我有一个排列列表（最多9个阶乘），并且它们中的每一个都被应用于512个整数的序列（每个整数一次）。 –
所以你有多达512倍你的程序的9个阶乘输出？ –