高速ビット順列

Question

16ビット整数に順列を格納して適用する必要があります。私が思いついた最善の解決策は、各4ビットは、i番目のビットの新しい位置に対応する64ビットの整数として格納順列​​であり、アプリケーションは次のようになり：

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によって処理することができ、シャッフルを適用するマルチプレクサへの入力であるマスクとしてエンコードされます。これは、ソフトウェアでも合理的に効率的に行うことができます（偉大ではありませんがOK）。これはバタフライ置換の単なる束です。マスクは計算するのが難しいですが、各ビットを単独で動かすよりも適用が速いのですが、それは扱うビット数に依存しますが、16はあまりありません。

シャッフルのいくつかの小さなカテゴリは、よりシンプルな（高速な）ネットワークで扱うことができます。これは、そのページでも見つけることができます。

最後に、現代のx86ハードウェアでは、（一般的に）単一サイクルで16バイトに置換（二重と零を含むことができる）を適用することができる多用途のpshufb関数があります。バイト上にビットを分配するのはslightly awkwardですが、そこにいればpshufbだけが置換され、pmovmskbが16ビットに圧縮されます。