相关疑难解决方法(0)

我有一些性能很重的代码执行位操作.它可以简化为以下明确定义的问题:

给定一个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)而不是条件跳转指令会更好吗？如果是,我如何让编译器为我生成这样的代码？
• 还有其他想法如何让它更快？
• 任何想法如何进行逆位图转换(我必须实现它,位不太重要)？

I would like to know if performing a logical right shift is faster when shifting by a power of 2

For example, is

myUnsigned >> 4

any faster than

myUnsigned >> 3

我很欣赏每个人的第一反应是告诉我,人们不应该担心像这样的小事,它使用正确的算法和集合来减少重要的数量级.我完全同意你的意见,但我真的想从嵌入式芯片(ATMega328)中挤出所有东西 - 我只是有一个性能转变,值得'哇喔!' 通过用位移替换除法,所以我向你保证这很重要.

我想通过重复每个位8次来膨胀unsigned char到a uint64_t.例如

char -> uint64_t
0x00 -> 0x00
0x01 -> 0xFF
0x02 -> 0xFF00
0x03 -> 0xFFFF
0xAA -> 0xFF00FF00FF00FF00

我目前有以下实现,使用位移来测试是否设置了一个位,以实现此目的:

#include <stdint.h>
#include <inttypes.h>   

#define BIT_SET(var, pos) ((var) & (1 << (pos)))

static uint64_t inflate(unsigned char a)
{
    uint64_t MASK = 0xFF;
    uint64_t result = 0;
    for (int i = 0; i < 8; i++) {
        if (BIT_SET(a, i))
            result |= (MASK << (8 * i));    
    }

    return result;
} 

但是,我对C来说还是个新手,所以这个摆弄个别位的东西让我有点不同,可能会有更好的(即更有效的)方法.

编辑添加
好了,所以在尝试了表查找解决方案后,结果如下.但是,请记住,我没有直接测试例程,而是作为更大函数的一部分(确切地说是二进制矩阵的乘法),因此这可能会影响结果的结果.因此,在我的计算机上,当乘以一百万个8x8矩阵时,编译为:

  gcc -O2 …