这两种方法如何找出2的幂是不同的？

Question

所以，假设我有一个数字N，保证它是2的幂，并且总是大于0。现在，我基于位运算符编写了两个C方法来查找2 N的幂-

方法A-

int whichPowerOf2(long long num) {
    int ret = -1;
    while (num) {
        num >>= 1;
        ret += 1;
    }

    return ret;
}

方法B-

int whichPowerOf2(long long num) {
    int idx = 0;
    while (!(num & (1<<idx))) idx += 1;
    return idx;
}

直觉上，这两种方法似乎是相同的，并且对于N的不同（较小）值也返回相同的值。但是，当我尝试提交编码问题的解决方案时，方法B对我不起作用。

谁能告诉我这是怎么回事？为什么方法A是正确的方法B是错误的？

Answer 1

在您的方法B中，以下行可能导致未定义的行为：

while (!(num & (1<<idx))) idx += 1;

为什么？好吧，表达式1<<idx被评估为int，因为常数1是int。此外，由于num是long long（我们假设它比int具有更多的位），所以您最终可能会向左移超过int中的位数。

要解决此问题，请在常量上使用LL后缀：

while (!(num & (1LL<<idx))) idx += 1;

Answer 2

问题在于此子表达式：

1<<idx

常量1的类型为int。如果idx大于int的位宽，则调用了undefined behavior。这是在C standard的6.5.7p3节中有关按位移位运算符的规定：

整数提升对每个操作数执行。方式结果是提升后的左操作数的结果。如果值右操作数为负或大于或等于宽度提升的左操作数的值，其行为是不确定的。

将常数更改为1LL，使其类型为long long，与num的类型匹配。

while (!(num & (1LL<<idx))) idx += 1;