是否有一个通用策略来创建一个有效的位置换算法?我们的目标是创建一个快速的无分支，如果可能的话，无lut算法。我举个例子:
按照以下规则表将一个13位码转换成另一个13位码:
对于位置换，已知有几种策略在某些情况下有效。在https://programming.sirrida.de/calcperm.php有一个代码生成器，它实现了其中的大部分。然而，在这种情况下，它似乎只找到了你建议的基本策略，这表明在这种排列中似乎很难找到任何可以利用的模式。
如果一个大的查找表太多，您可以尝试使用两个较小的查找表。
-
取输入的低7位，在表a中查找16位值。
-
取输入的高6位，在表b中查找一个16位的值。
-
or从1。和2。生成结果。
表A需要128*2字节，表B需要64*2字节，即查找表的384字节。
这是一个手动优化的多重LUT解决方案，除了证明我有一些时间可以消耗之外，它并没有真正证明任何东西。
多个小查找表偶尔可以节省时间和/或空间，但我不知道找到最佳组合的策略。在这种情况下，最好的除法似乎是3个lut，每个lut有3位(4- 6,7 -9和10-12位)，总共24字节(每个表有8个单字节条目)，加上一个简单的移位来覆盖到3位，再加上一个简单的移位来覆盖剩余的位0。第5位，它是未转换的，也是一个诱人的目标，但我没有看到一个好的方法来划分它周围的位范围。
这三个查询表都有单字节条目，因为每个范围的转换范围只有一个字节。事实上，两个位范围的转换完全适合低阶字节，避免了移位。
代码如下:
unsigned short permute_bits(unsigned short x) {
#define LUT3(BIT0, BIT1, BIT2)
{ 0, (BIT0), (BIT1), (BIT1)+(BIT0),
(BIT2), (BIT2)+(BIT0), (BIT2)+(BIT1), (BIT2)+(BIT1)+(BIT0)}
static const unsigned char t4[] = LUT3(1<<(6-3), 1<<(5-3), 1<<(9-3));
static const unsigned char t7[] = LUT3(1<<4, 1<<3, 1<<1);
static const unsigned char t10[] = LUT3(1<<0, 1<<2, 1<<7);
#undef LUT3
return ( (x&1) << 8) // Bit 0
+ ( (x&14) << 9) // Bits 1-3, simple shift
+ (t4[(x>>4)&7] << 3) // Bits 4-6, see below
+ (t7[(x>>7)&7] ) // Bits 7-9, three-bit lookup for LOB
+ (t10[(x>>10)&7] ); // Bits 10-12, ditto
}
4-6位注释
第6位被转换为位于低阶字节之外的第9位。然而，第4位和第5位分别被移动到第6位和第5位，并且变换后的位的总范围只有5位。几个不同的最终移位是可能的，但是保持相对较小的移位在x86架构上提供了一个微小的改进，因为它允许使用LEA同时进行移位和添加(参见下面的汇编中的最后第二条指令)。
中间结果被添加，而不是出于同样的原因使用布尔或。由于每个中间结果的位集是不相交的，所以ADD和OR的结果是相同的;使用add可以利用芯片的特性，如LEA。
下面是该函数的编译，取自http://gcc.godbolt.org，使用gcc 12.1和-O3:
permute_bits(unsigned short):
mov edx, edi
mov ecx, edi
movzx eax, di
shr di, 4
shr dx, 7
shr cx, 10
and edi, 7
and edx, 7
and ecx, 7
movzx ecx, BYTE PTR permute_bits(unsigned short)::t10[rcx]
movzx edx, BYTE PTR permute_bits(unsigned short)::t7[rdx]
add edx, ecx
mov ecx, eax
sal eax, 9
sal ecx, 8
and ax, 7168
and cx, 256
or eax, ecx
add edx, eax
movzx eax, BYTE PTR permute_bits(unsigned short)::t4[rdi]
lea eax, [rdx+rax*8]
ret
我省略了查找表本身，因为GCC生成的程序集不是很有用。
我不知道这是否比@trincot的解决方案更快(在评论中);快速基准测试没有定论，但它看起来快了几个百分点。但是它相当短，可能足以弥补24字节的查找数据。