c++ - 评估一个数是否是 4 的整数幂

Question

声称下面的函数是用来判断一个数是否是4的整数次幂。我不太明白它是怎么工作的？

bool fn(unsigned int x)
{
if ( x == 0 ) return false;
if ( x & (x - 1) ) return false;
return x & 0x55555555;
}

Answer 1

第一个条件排除 0，这显然不是 4 的幂，但会错误地通过以下两个测试。 (编辑:不，它不会，正如所指出的那样。第一个测试是多余的。)

下一个是一个不错的技巧:当且仅当数字是 2 的幂时，它才返回 true。2 的幂的特征是只设置一个位。设置了一位的数字减去 1 会导致该数字之前的所有位都被设置(即 0x1000 减一为 0x0111)。和这两个数字，你得到 0。在任何其他情况下(即不是 2 的幂)，至少会有一位重叠。

所以在这一点上，我们知道它是 2 的幂。

x & 0x55555555 如果设置了任何偶数位(位 0、位 2、位 4、位 6 等)，则返回非零 (=true)。这意味着它是 4 的幂。(即 2 次未通过，但 4 次通过，8 次未通过，16 次通过等)。