我有一些执行位操作的性能密集型代码。它可以简化为以下明确定义的问题:
给定一个 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) 代替条件跳转指令会更好吗？如果是，我怎样才能让编译器为我生成这样的代码？
- 关于如何让它更快的任何其他想法？
- 知道如何进行逆向位图转换(我也必须实现它，但它不太重要)？
最佳答案
有一个聪明的方法可以做到这一点，在这里可能会有帮助。它实际上 解决了一个稍微更一般的位改组问题。你的问题有一个 输入:
+---------------+---------------+---------------+---------------+
|0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0|0 0 0 a b c d e|f g h i j k l m|
+---------------+---------------+---------------+---------------+
....但是让我们考虑所有的位:
+---------------+---------------+---------------+---------------+
|A B C D E F G H|I J K L M N O P|Q R S a b c d e|f g h i j k l m|
+---------------+---------------+---------------+---------------+
并尝试像这样交错它们:
+---------------+---------------+---------------+---------------+
|A Q B R C S D 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
v v v v v
+---------------+---------------+---------------+---------------+
| |I J K L M N O P|Q R S a b c d e| |
+---------------+---------------+---------------+---------------+
构造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;:
+---------------+---------------+---------------+---------------+
|A B C D E F G H|I J K L M N O P|Q R S a b c d e|f g h i j k l m| input
+---------------+---------------+---------------+---------------+
exclusive-OR with:
+---------------+---------------+---------------+---------------+
|0 0 0 0 0 0 0 0|A B C D E F G H|I J K L M N O P|Q R S a b c d e| 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));
导致:
+---------------+---------------+---------------+---------------+
|A B C D E F G H|Q R S a b c d e|I J K L M N O P|f g h i j k l m| input
+---------------+---------------+---------------+---------------+
下一步，分而治之...进行类似的中间交换 左手一半的位:
+---------------+---------------+---------------+---------------+
|A B C D E F G H|Q R S a b c d e| | |
+---------------+---------------+---------------+---------------+
becomes
+---------------+---------------+---------------+---------------+
|A B C D Q R S a|E F G H b c d e| | |
+---------------+---------------+---------------+---------------+
...和右半边:
+---------------+---------------+---------------+---------------+
| | |I J K L M N O P|f g h i j k l m|
+---------------+---------------+---------------+---------------+
becomes
+---------------+---------------+---------------+---------------+
| | |I J K L f g h i|M N O P j k l m|
+---------------+---------------+---------------+---------------+
我们可以使用与第一步完全相同的技巧，因为我们想要 对 32 位字的两个 16 位半部分执行完全相同的操作， 我们可以并行进行:
tmp = (input ^ (input >> 4)) & 0x00f000f0;
构造我们将用于交换的两对 4 位，然后
input ^= (tmp ^ (tmp << 4));
实际进行交换。
我们可以继续应用相同的原则，直到交换完成。
每个点参与交换的比特用#标记:
+---------------+---------------+---------------+---------------+
|A B C D E F G H|I J K L M N O P|Q R S a b c d e|f g h i j k l m|
+---------------+---------------+---------------+---------------+
###############/###############
+---------------+---------------+---------------+---------------+
|A B C D E F G H|Q R S a b c d e|I J K L M N O P|f g h i j k l m|
+---------------+---------------+---------------+---------------+
#######/####### #######/#######
+---------------+---------------+---------------+---------------+
|A B C D Q R S a|E F G H b c d e|I J K L f g h i|M N O P j k l m|
+---------------+---------------+---------------+---------------+
###/### ###/### ###/### ###/###
+---------------+---------------+---------------+---------------+
|A B Q R C D S a|E F b c G H d e|I J f g K L h i|M N j k O P l m|
+---------------+---------------+---------------+---------------+
#/# #/# #/# #/# #/# #/# #/# #/#
+---------------+---------------+---------------+---------------+
|A Q B R C S D 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));
尽管您可以针对您的特定应用对此进行改进， 如果已知所有其他位都为零:请参阅我对另一个的回答 问题 here .
最后一点，不要相信任何人关于相对性能的任何说法 此处建议的任何方法都没有在您的中对其进行基准测试 申请。 (特别是，大型查找表看起来会好得多 在简单的微基准测试中，它们实际上在给定的真实环境中 应用程序，由于从缓存中逐出大量其他数据， 这会对外部循环产生负面影响。)
关于c - 如何在位图中的位之间插入零？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4597940/