c++ - 有没有更有效的方法来获取以字节为单位的 32 位整数的长度？

Question

我想要以下小功能的快捷方式，其中 性能非常重要(该函数被调用超过 10.000.000 次):

inline int len(uint32 val)
{
    if(val <= 0x000000ff) return 1;
    if(val <= 0x0000ffff) return 2;
    if(val <= 0x00ffffff) return 3;
    return 4;
} 

有谁知道...一个很酷的位操作技巧？ 提前感谢您的帮助!

Answer 1

这个怎么样？

inline int len(uint32 val)
{
    return 4
        - ((val & 0xff000000) == 0)
        - ((val & 0xffff0000) == 0)
        - ((val & 0xffffff00) == 0)
    ;
}

删除 inline 关键字，g++ -O2 将其编译为以下无分支代码:

movl    8(%ebp), %edx
movl    %edx, %eax
andl    $-16777216, %eax
cmpl    $1, %eax
sbbl    %eax, %eax
addl    $4, %eax
xorl    %ecx, %ecx
testl   $-65536, %edx
sete    %cl
subl    %ecx, %eax
andl    $-256, %edx
sete    %dl
movzbl  %dl, %edx
subl    %edx, %eax

如果您不介意特定于机器的解决方案，您可以使用搜索前 1 位的 bsr 指令。然后您只需除以 8 即可将位转换为字节并加 1 以将范围 0..3 移动到 1..4:

int len(uint32 val)
{
    asm("mov 8(%ebp), %eax");
    asm("or  $255, %eax");
    asm("bsr %eax, %eax");
    asm("shr $3, %eax");
    asm("inc %eax");
    asm("mov %eax, 8(%ebp)");
    return val;
}

请注意，我不是内联汇编之神，所以也许有更好的解决方案来访问 val 而不是显式寻址堆栈。但是你应该明白基本的想法。

GNU 编译器还有一个有趣的内置函数，称为 __builtin_clz:

inline int len(uint32 val)
{
    return ((__builtin_clz(val | 255) ^ 31) >> 3) + 1;
}

在我看来，这比内联汇编版本好多了:)