有没有更有效的方法来获取32位整数的字节长度？
我想要以下小函数的快捷方式，其中性能非常重要(该函数被调用超过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;
} 有没有人知道...一个很酷的位操作技巧？提前感谢您的帮助！
回答 12
Stack Overflow用户
发布于 2010-08-31 00:09:19
这个怎么样？
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如果您不介意特定于机器的解决方案，您可以使用bsr指令来搜索前1位。然后，您只需除以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;
}在我看来，这比内联程序集版本要好得多:)
Stack Overflow用户
发布于 2010-08-31 01:00:02
我做了一个小型的不科学的基准测试，只是在VS2010编译器下从0到MAX_LONG的循环中调用函数时，测量GetTickCount()调用的差异。
这是我看到的：
这花了11497个刻度
inline int len(uint32 val)
{
if(val <= 0x000000ff) return 1;
if(val <= 0x0000ffff) return 2;
if(val <= 0x00ffffff) return 3;
return 4;
} 虽然这需要14399个刻度
inline int len(uint32 val)
{
return 4
- ((val & 0xff000000) == 0)
- ((val & 0xffff0000) == 0)
- ((val & 0xffffff00) == 0)
;
}编辑:我关于为什么一个更快的想法是错误的，因为：
inline int len(uint32 val)
{
return 1
+ (val > 0x000000ff)
+ (val > 0x0000ffff)
+ (val > 0x00ffffff)
;
}这个版本只使用了11107个刻度。因为+可能比-更快？我没有把握。
不过，二进制搜索速度更快，达到了7161次
inline int len(uint32 val)
{
if (val & 0xffff0000) return (val & 0xff000000)? 4: 3;
return (val & 0x0000ff00)? 2: 1;
}到目前为止，最快的是使用MS内部函数，速度为4399次
#pragma intrinsic(_BitScanReverse)
inline int len2(uint32 val)
{
DWORD index;
_BitScanReverse(&index, val);
return (index>>3)+1;
}作为参考-这是我用来分析的代码：
int _tmain(int argc, _TCHAR* argv[])
{
int j = 0;
DWORD t1,t2;
t1 = GetTickCount();
for(ULONG i=0; i<-1; i++)
j=len(i);
t2 = GetTickCount();
_tprintf(_T("%ld ticks %ld\n"), t2-t1, j);
t1 = GetTickCount();
for(ULONG i=0; i<-1; i++)
j=len2(i);
t2 = GetTickCount();
_tprintf(_T("%ld ticks %ld\n"), t2-t1, j);
}我必须打印j以防止循环被优化出来。
Stack Overflow用户
发布于 2010-08-31 00:17:56
您是否真的有个人资料证据表明这是您的应用程序中的一个重要瓶颈？只要以最明显的方式来做，并且只有当分析显示它是一个问题时(我怀疑)，然后尝试改进事情。最有可能的情况是，通过减少对此函数的调用次数，而不是通过更改其中的某些内容，您将获得最佳的改进。
https://stackoverflow.com/questions/3602079
复制相似问题