通过 C 中的直线位操作找到正整数的最高有效位或对数基数 2(floor)

Question

这是我需要做的：

int lg(int v)
{
    int r = 0;
    while (v >>= 1) // unroll for more speed...
    {
        r++;
    }
}

我在以下位置找到了上述解决方案：http://graphics.stanford.edu/~seander/bithacks.html#IntegerLog

这有效，但我需要在没有循环、控制结构或大于 0xFF （255） 的常量的情况下做到这一点，事实证明这对我来说很难找到。 我一直试图使用形式的条件来弄清楚一些事情

( x ? y : z ) = (((~(!!x) + 1)) & y) | ((~(~(!!x) + 1)) & z)

但我无法让它工作。 谢谢你的时间。

Answer 1

无需任何控制结构，甚至无需?:运算符，即可模拟自己的算法

int r = 0;
x >>= 1;
r += (x != 0);
x >>= 1;
r += (x != 0);
...

前提是，在 C 中，

• 假设 x 为正数（否则int x=-1;例如 x >>= 1 n 次总是!= 0
• 像 x != 0 这样的条件返回 0（假）或 1（*真）

Answer 2

这听起来像是家庭作业。好吧，如果你不能使用控制结构，一个好的选择是预先计算你能做的：分而治之。求解较小的部分（一个字节，一个半字节，您的选择），并应用于整数的部分。