如何在位图中的位之间插入零？
我有一些性能很重的代码执行位操作。 它可以简化为以下明确定义的问题：
给定一个13位位图，构造一个26位位图，其中包含在偶数位置间隔的原始位 。
为了显示：
0000000000000000000abcdefghijklm (input, 32 bits) 0000000a0b0c0d0e0f0g0h0i0j0k0l0m (output, 32 bits) 我目前在C中以下列方式实现它：
if (input & (1 << 12)) output |= 1 << 24; if (input & (1 << 11)) output |= 1 << 22; if (input & (1 << 10)) output |= 1 << 20; ...
我的编译器（MS Visual Studio）将其转换为以下内容：
test eax,1000h jne 0064F5EC or edx,1000000h ... (repeated 13 times with minor differences in constants)
我想知道我能不能做得更快。 我想用C语言编写代码，但是可以切换到汇编语言。
- 我可以使用一些MMX / SSE指令一次处理所有位吗？
- 也许我可以使用乘法？ （乘以0x11111111或其他一些神奇的常数）
- 使用条件设置指令（SETcc）而不是条件跳转指令会更好吗？ 如果是，我如何让编译器为我生成这样的代码？
- 还有其他想法如何让它更快？
- 任何想法如何进行逆位图转换（我必须实现它，位不太重要）？
使用查找表执行此操作。 2 ^ 13听起来像很多条目，但它们很容易适应CPU缓存。
哦，如果其他19位中有垃圾，你需要先将它们屏蔽掉。
有一种聪明的方法可以在这里做到这一点。 它实际上解决了一个稍微更普遍的位改组问题。 您的问题输入：
+---------------+---------------+---------------+---------------+ |0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0|0 0 0 abcde|fghijklm| +---------------+---------------+---------------+---------------+
….但是让我们考虑所有的事情：
+---------------+---------------+---------------+---------------+ |ABCDEFGH|IJKLMNOP|QRS abcde|fghijklm| +---------------+---------------+---------------+---------------+
并尝试将它们全部交错：
+---------------+---------------+---------------+---------------+ |AQBRCSD a|E b F c G d H e|I f J g K h L i|M j N k O l P m| +---------------+---------------+---------------+---------------+
第一步，考虑输入的中间部分：
bit 31 24 16 8 0 vvvvv +---------------+---------------+---------------+---------------+ | |IJKLMNOP|QRS abcde| | +---------------+---------------+---------------+---------------+
构造8比特值：{ I^Q ， J^R ， K^S ， L^a ， M^b ， N^c ， O^d ， P^e }。
如果我们将这个8位值与位[15：8]异或，并且还使用位[23:16]对相同的8位值进行异或，我们将交换中间两个字节：例如，位23 （原来I ）将成为I ^ (I^Q) = Q和第15位（原Q ）将成为Q ^ (I^Q) = I
为此： tmp = (input ^ (input >> 8)) & 0x0000ff00; ：
+---------------+---------------+---------------+---------------+ |ABCDEFGH|IJKLMNOP|QRS abcde|fghijklm| input +---------------+---------------+---------------+---------------+ exclusive-OR with: +---------------+---------------+---------------+---------------+ |0 0 0 0 0 0 0 0|ABCDEFGH|IJKLMNOP|QRS abcde| input >> 8 +---------------+---------------+---------------+---------------+ -->|want these bits|<-- mask (bitwise AND) with 0x0000ff00: +---------------+---------------+---------------+---------------+ |0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0|1 1 1 1 1 1 1 1|0 0 0 0 0 0 0 0| 0x0000ff00 +---------------+---------------+---------------+---------------+
现在我们需要的8位值是位[15：8]，其他所有位都是0.现在我们可以用
input ^= (tmp ^ (tmp << 8));
导致：
+---------------+---------------+---------------+---------------+ |ABCDEFGH|QRS abcde|IJKLMNOP|fghijklm| input +---------------+---------------+---------------+---------------+
对于下一步，分而治之......执行左半部分中间位的类似交换：
+---------------+---------------+---------------+---------------+ |ABCDEFGH|QRS abcde| | | +---------------+---------------+---------------+---------------+ becomes +---------------+---------------+---------------+---------------+ |ABCDQRS a|EFGH bcde| | | +---------------+---------------+---------------+---------------+
......和右半边：
+---------------+---------------+---------------+---------------+ | | |IJKLMNOP|fghijklm| +---------------+---------------+---------------+---------------+ becomes +---------------+---------------+---------------+---------------+ | | |IJKL fghi|MNOP jklm| +---------------+---------------+---------------+---------------+
我们可以使用与第一步完全相同的技巧，因为我们希望在32位字的两个16位半部分执行完全相同的操作，我们可以并行执行：
tmp = (input ^ (input >> 4)) & 0x00f000f0;
构造我们将用于交换的两对4位，然后
input ^= (tmp ^ (tmp << 4));
实际上做交换。
在交换完成之前，我们可以继续应用相同的原则。 在每个点参与交换的位用#标记：
+---------------+---------------+---------------+---------------+ |ABCDEFGH|IJKLMNOP|QRS abcde|fghijklm| +---------------+---------------+---------------+---------------+ ###############/############### +---------------+---------------+---------------+---------------+ |ABCDEFGH|QRS abcde|IJKLMNOP|fghijklm| +---------------+---------------+---------------+---------------+ #######/####### #######/####### +---------------+---------------+---------------+---------------+ |ABCDQRS a|EFGH bcde|IJKL fghi|MNOP jklm| +---------------+---------------+---------------+---------------+ ###/### ###/### ###/### ###/### +---------------+---------------+---------------+---------------+ |ABQRCDS a|EF bc GH de|IJ fg KL hi|MN jk OP lm| +---------------+---------------+---------------+---------------+ #/# #/# #/# #/# #/# #/# #/# #/# +---------------+---------------+---------------+---------------+ |AQBRCSD a|E b F c G d G e|I f J g K h L i|M j N k O l P m| +---------------+---------------+---------------+---------------+
码：
tmp = (input ^ (input >> 8)) & 0x0000ff00; input ^= (tmp ^ (tmp << 8)); tmp = (input ^ (input >> 4)) & 0x00f000f0; input ^= (tmp ^ (tmp << 4)); tmp = (input ^ (input >> 2)) & 0x0c0c0c0c; input ^= (tmp ^ (tmp << 2)); tmp = (input ^ (input >> 1)) & 0x22222222; input ^= (tmp ^ (tmp << 1)); /* = output */
可以通过向后运行4个步骤来执行反向操作：
tmp = (input ^ (input >> 1)) & 0x22222222; input ^= (tmp ^ (tmp << 1)); /* = output */ tmp = (input ^ (input >> 2)) & 0x0c0c0c0c; input ^= (tmp ^ (tmp << 2)); tmp = (input ^ (input >> 4)) & 0x00f000f0; input ^= (tmp ^ (tmp << 4)); tmp = (input ^ (input >> 8)) & 0x0000ff00; input ^= (tmp ^ (tmp << 8));
虽然您可能能够针对您的特定应用对此进行改进，但如果已知其他每个位为零：请参阅此处对其他问题的回答。
最后要注意的是，如果没有在您的应用程序中对它们进行基准测试，请不要相信任何人对此处建议的任何方法的相对性能所说的话。 （特别是，由于从缓存中驱逐大量其他数据，大型查找表在简单的微基准测试中看起来比实际在给定的实际应用中实际上要好得多，这可能对外部循环产生负面影响（S）。）
你可以这样做：
; eax = input bits shrd edx,eax,2 shr eax,1 shrd edx,eax,2 shr eax,1 shrd edx,eax,2 shr eax,1 shrd edx,eax,2 shr eax,1 shrd edx,eax,2 shr eax,1 shrd edx,eax,2 shr eax,1 shrd edx,eax,2 shr eax,1 shrd edx,eax,2 shr eax,1 shrd edx,eax,2 shr eax,1 shrd edx,eax,2 shr eax,1 shrd edx,eax,2 shr eax,1 shrd edx,eax,2 shr eax,1 shrd edx,eax,8 and edx,0x01555555 ; edx = output
不要使用分支：
output = (input & 1) | ((input & 2) << 1) | ((input & 4) << 2) | ((input & 8) << 3) | ((input & 16) << 4) /* etc. */
这是一个可能更容易阅读/理解同一件事的版本：
output = ((input & (1 << 0)) << 0) | ((input & (1 << 1)) << 1) | ((input & (1 << 2)) << 2) | ((input & (1 << 3)) << 3) | ((input & (1 << 4)) << 4) | ((input & (1 << 5)) << 5) | ((input & (1 << 6)) << 6) | ((input & (1 << 7)) << 7) | ((input & (1 << 8)) << 8) | ((input & (1 << 9)) << 9) | ((input & (1 << 10)) << 10) | ((input & (1 << 11)) << 11) | ((input & (1 << 12)) << 12);
我将给出一个无条件的算法（只有加法和按位运算），我相信这将比你当前的解决方案更快。
这是13位的C代码。 下面是一个说明该方法如何适用于3位的说明，我希望这种概括是明确的。
（注意：代码是循环展开的。一个好的编译器会为你做这个，所以你可以将它压缩成一个循环。）
unsigned mask, output; unsigned x = input; mask = ((1<<13)-1) << 13; x = (x + mask) & ~mask; mask = ((1<<12)-1) << 12; x = (x + mask) & ~mask; ... mask = ((1<<3)-1) << 3; x = (x + mask) & ~mask; mask = ((1<<2)-1) << 2; x = (x + mask) & ~mask; mask = ((1<<1)-1) << 1; x = (x + mask) & ~mask; output = x;
现在，这是3位方法的解释。 初始状态为'00abc'。 首先将'a'两个位置向左移动，方法是添加01100，然后与10011进行AND运算（这恰好是前一个数字的按位NOT）。 这是如何适用于a = 0,1（第一个箭头是加法，第二个箭头是AND）：
a = 0：00abc = 000bc - > 011bc - > 000bc = a00bc
a = 1：00abc = 001bc - > 100bc - > 100bc = a00bc
接下来，通过添加00010然后与10101进行AND运动将'b'向左移动一个位置：
b = 0：a00bc = a000c - > a001c - > a000c = a0b0c
b = 1：a00bc = a001c - > a010c - > a010c = a0b0c
而已。
首先，对于“26位”值，最高位应始终清零，因此它实际上是25位值。
1）MMX（和/或SSE）无济于事，因为主要的问题是没有简单的算术或布尔运算系列可以得到你想要的结果，并且所有东西都支持相同的算术和布尔运算。
2）我无法想到或找到乘法的魔法常数。
3）我看不到使用任何条件设置指令（例如SETcc）的方法，它比移位/添加指令有任何优势。
4）jdv和paul（上图）是对的。 如果您需要经常进行此转换以至于性能很重要，那么查找表将是现代CPU上最佳/最快的选项。 “13位到26位”的查找表是2 ** 13个双字或32 KiB。 在旧的CPU（具有小的L1高速缓存）上，CPU速度和RAM速度之间的相对差异并不像现在那么糟糕。
如果你不能为“13位到25位”查找表节省32 KiB，你可以将13位值分成一对值（一个6位值和一个7位值），然后在组合结果之前，在每个值上使用查找表，如下所示：
mov ebx,eax ;ebx = 13-bit value shr eax,6 ;eax = highest 7 bits of value and ebx,0x003F ;ebx = lowest 6 bits of value mov eax,[lookup_table + eax*2] ;eax = highest 14-bits of result mov ebx,[lookup_table + ebx*2] ;eax = lowest 12-bits of result shl eax,12 or eax,ebx ;eax = 25-bit result
在这种情况下，查找表有128个条目（每个条目2个字节），因此它只有256个字节。
5）对于反向操作，一个简单的查找表将花费你64 MiB（2 ** 25 * 2），所以这不是一个好主意。 但是，您可以将25位值拆分为13位值和11位值（12位值，其中最高位始终清除），并使用8192条目表，每个条目一个字节（总计成本是8 KiB）。 没有理由你不能将25位值拆分成更多/更小的块（并使用更小的表）。
在从Haswell开始的Intel x86处理器上，您可以使用BMI2指令集中的单个pdep指令来执行此操作：
uint32_t interleave_zero_bits(uint32_t x) { return _pdep_u32(x, 0x55555555U); }
我认为这可能是相关的，但我不完全确定。 我知道MMX指令用于交错32/64位值的字节，但不是单个位。
你没有指定要运行的平台，我想尝试一种与已经发布的平台不同的方法（我喜欢查找表一，它可以正常工作，直到位数增加）。
大多数平台都有单独的移位和旋转指令。 几乎总是有一条包含进位/溢出标志的指令，因此您可以“移入”您想要的位。 假设我们有这些指令：* SHIFTLEFT：执行leftshift并用零填充低位。 * ROTATELEFT：执行leftshift，从进位标志中的前一个值设置最低位，并从左侧“向外”移位的位设置进位。
伪代码：
LOAD value into register A; LOAD 0 into register B; SHIFT register A (registerwidth-13) times; ROTATELEFT A ROTATELEFT B SHIFTLEFT B
…重复13次。 随便展开。
第一个class次应该在进位之前将最上面的位置到位。 ROTATELEFT A将MSB推入进位，ROTATELEFT B将该位推入B的LSB，SHIFTLEFT B将0输入。对所有位执行此操作。
编辑/添加时间：
您可以使用相同的指令执行相反的操作（反向位图转换），如下所示：
LOAD值进入寄存器A; 将0加载到寄存器B中;
ROTATELEFT A; ROTATELEFT A; ROTATELEFT B; …重复13次然后SHIFTLEFT B; for（registerwidth-13）次。
LSB携带; 忘记它，接下来LSB进入进位，把它放入目标寄存器，重复所有位，然后对齐结果。
你总是可以使用for循环：
for (int i = 0; i < 13; i++) { output |= (input & (1 << i)) << i; }
这个更短，但我认为它的速度要快得多。
检查你的CPU是否支持字节和字交换（对于字节序转换） – 如果是这样 – 只需对它进行交换 – 这将是一些较短的6（5）指令。