[LeetCode] 231. Power of Two

链接：231. Power of Two

描述：判断给定的整数是否是 2 的幂。

举例：2⁰=1, 2¹=2, 2²=4 中，1,2,4 就是2的幂。

思路：可以基于两种基本策略:

• 根据十进制值
• 根据二进制值。

十进制的方式对人类来说较友好，但偏低效；二进制的方式机器来说较友好，通常也更高效。

这道的解法太多，我就随便找一个简单的。

可以先看一下是 2 的幂的数的二进制表示：

真值    补码
-----------------
1       0000 0001
2       0000 0010
4       0000 0100
8       0000 1000
16      0001 0000
32      0010 0000
64      0100 0000
128     1000 0000
...     .... ....

可以看出，如果一个数是 2 的幂，那么它只有一位二进制位是 1。（这并不是简单的以偏概全，由现象推结论）

由于只有一个二进制位，于是可以顺便再看下比它小 1 的值，以及它们的位与值：

真值    补码            比它小 1 的值   按位与值
------------------------------------------------
1       0000 0001       0000 0000       0
2       0000 0010       0000 0001       0
4       0000 0100       0000 0011       0
8       0000 1000       0000 0111       0
16      0001 0000       0000 1111       0
32      0010 0000       0001 1111       0
64      0100 0000       0011 1111       0
128     1000 0000       0111 1111       0
...     .... ....

所以，算法就已经浮现了：

1
2
3
4

bool isPowerOfTwo(unsigned int x)
{
    return x != 0 && (x & (x - 1)) == 0;
}

Google之时，在 Exploring Binary 上面看到了作者给出了 10 种解决方案，有兴趣可以看看。从作者域名上看，他应该是探索二进制方面的专家。