计算只有位设置的数字的最快方法是哪一个是另一个数字中设置的最高位？

Question

可能重复:
先前的2次幂
获取最左边的位

我想要的是,假设有一个数字5即101.我的答案应该是100.对于9ie 1001,答案应该是1000

Answer 1

如果不对必须运行的机器给出约束,则不能要求最快的序列.例如,某些机器支持称为"计数前导零"的指令,或者具有非常快速地模拟它的方法.如果您可以访问此指令(例如使用gcc),那么您可以编写:

#include <limits.h>
#include <stdint.h>
uint32_t f(uint32_t x) 
{
    return ((uint64_t)1)<<(32-__builtin_clz(x)-1);
}
int main()
{
    printf("=>%d\n",f(5));
    printf("=>%d\n",f(9));
}

f(x)返回你想要的东西(x> = y且y = 2**n的y最小).编译器现在将为目标机器生成最佳代码序列.例如,在编译默认的x86_64体系结构时,f()看起来像这样:

    bsrl    %edi, %edi
    movl    $31, %ecx
    movl    $1, %eax
    xorl    $31, %edi
    subl    %edi, %ecx
    salq    %cl, %rax
    ret

你看,这里没有循环!7条说明,没有分支机构.

但是,如果我告诉我的编译器(gcc-4.5)优化我正在使用的机器(AMD Phenom-II),那么这就出现在f()中:

    bsrl    %edi, %ecx
    movl    $1, %eax
    salq    %cl, %rax
    ret

这可能是这台机器最快的方法.

编辑: f(0)会导致UB,我已经修复了(和程序集).另外,uint32_t意味着我可以写出32而不会感到内疚:-)

Answer 2

来自Hacker's Delight,一个不错的无分支解决方案:

uint32_t flp2 (uint32_t x)
{
    x = x | (x >> 1);
    x = x | (x >> 2);
    x = x | (x >> 4);
    x = x | (x >> 8);
    x = x | (x >> 16);
    return x - (x >> 1);
}

这通常需要12条指令.如果您的CPU具有"计数前导零"指令,则可以减少执行此操作.