如何插入位之间的零位图中？ [英] How to insert zeros between bits in a bitmap?

问题描述

我有一些性能重code执行位操作。它可以降低到下面的明确定义的问题：

I have some performance-heavy code that performs bit manipulations. It can be reduced to the following well-defined problem:

给定一个13位的位图，构造包含在偶数位置间隔原始位的26位的位图

要说明：

0000000000000000000abcdefghijklm (input, 32 bits)
0000000a0b0c0d0e0f0g0h0i0j0k0l0m (output, 32 bits)

目前，我有它的实现方式是在C：

I currently have it implemented in the following way in 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中）变成下面这样：

My compiler (MS Visual Studio) turned this into the following:

test        eax,1000h
jne         0064F5EC
or          edx,1000000h
... (repeated 13 times with minor differences in constants)

我不知道我是否可以使任何更快。我想有我的code C语言编写的，但切换到汇编语言是可能的。

I wonder whether i can make it any faster. I would like to have my code written in C, but switching to assembly language is possible.

• 我可以使用一些MMX / SSE指令同时处理所有位？


• 也许我可以用乘法来算？ （乘以0x11111111或其他一些神奇的常数）


• 会不会更好使用条件设置指令（SETcc）代替条件跳转指令？如果是的话，我怎样才能让编译器产生这样code给我吗？


• 任何其他想法如何使它更快吗？


• 任何想法如何做逆位图转换（我要实现它太，咬它是那么重要）？

推荐答案

通过查找表就这样做。 2 ^ 13的声音就像一个条目很多，但他们会很容易融入CPU高速缓存。

Do it with a lookup table. 2^13 sound like a lot of entries but they will easily fit into the CPU cache.

哦，如果有在其他19位是垃圾，你需要先屏蔽出来。

Oh, and if there's garbage in the other 19 bits, you need to mask them out first.

这篇关于如何插入位之间的零位图中？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！