c - 求 2 的幂的优雅方法

Question

我的问题与 Fastest way of computing the power that a "power of 2" number used? 非常相似:

将 x=2^y 作为输入，我想输出 y。不同之处在于我使用 C 而不是 C++ 进行编码，而且我确信我的输入中只设置了一位，所以我想知道是否有更有效的方法来解决这个问题。

这是我的尝试:

unsigned int get_power_of_two(unsigned int x)
{
    unsigned int y=0;
    for(unsigned int input=x; input>0; input=input>>1)
    {
        if(input & 1U)
        {
            break;
        }
        y++;
    }
    return y;
}

与@Dave 的回答中建议的查找表相比，这种效率如何？(同样，我用 C 编写代码，所以我没有像 lower_bound 这样的迭代器函数)

Answer 1

您的算法的效率是 O(log x)，而 Dave 的(对 2 的幂执行二进制搜索)是 O(log log x)。所以他的渐近速度更快。

当然，最快的方法是使用 BSF 指令。