这两种计算 2 的幂的方法有何不同？

Question

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

方法 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;
}

直觉上，这两种方法看起来是一样的，而且 return 对于 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. This is specified in section 6.5.7p3 of the C standard 关于移位运算符：

The integer promotions are performed on each of the operands. The type of the result is that of the promoted left operand. If the value of the right operand is negative or is greater than or equal to the width of the promoted left operand, the behavior is undefined.

将常量更改为 1LL 以赋予其类型 long long，匹配 num 的类型。

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

这两种计算 2 的幂的方法有何不同？

How are these two methods to find what power of 2 a number is, different?

c

bit-manipulation

bitmask

bit-shift

bitwise-operators