评估数字是否为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减去1为0x0111).和那两个数字,你得到0.在任何其他情况下(即不是2的幂),将至少有一个重叠的位.

所以在这一点上,我们知道这是2的力量.

x & 0x55555555如果设置了任何偶数位(位0,位2,位4,位6等),则返回非零(=真).这意味着它的力量为4.(即2不通过,但4次通过,8次不通过,16次通过等).