评估数字是否为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返回非零（= true）（位0，位2，位4，位6等）。这意味着它的力量为4.（即2不通过，但4次通过，8次不通过，16次通过等）。

Answer 2

4的每个幂必须是1的形式，后跟偶数个零（二进制表示）：100 ... 00：

100 = 4

10000 = 16

1000000 = 64

1. 第一次测试（“如果”）是显而易见的。
2. 当从XY100 ... 00的形式中减去1时，得到XY011 ... 11。因此，第二个测试检查数字中是否有多个“1”位（本例中为XY）。
3. 最后一个测试检查这个单个“1”是否在正确位置，即位＃2,4,6等。如果不是，则屏蔽（＆）将返回非零结果。

Answer 3

以下解决方案适用于2,4,16检查功率。

  public static boolean isPowerOf(int a, int b)
  {         
     while(b!=0 && (a^b)!=0)
     {              
        b = b << 1;     
     }
   return (b!=0)?true:false;   
  }

isPowerOf(4,2) > true
isPowerOf(8,2) > true
isPowerOf(8,3) > false
isPowerOf(16,4) > true