链接:[231. Power of Two](https://leetcode.com/problems/power-of-two/) 描述:判断给定的整数是否是 2 的幂。 举例:20=1, 21=2, 22=4 中,1,2,4 就是2的幂。 思路:可以基于两种基本策略: - 根据十进制值 - 根据二进制值。 十进制的方式对人类来说较友好,但偏低效;二进制的方式机器来说较友好,通常也更高效。 这道的解法太多,我就随便找一个简单的。 可以先看一下是 2 的幂的数的二进制表示: ```none 真值 补码 ----------------- 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 的值,以及它们的位与值: ```none 真值 补码 比它小 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 ... .... .... ``` 所以,算法就已经浮现了: ```c bool isPowerOfTwo(unsigned int x) { return x != 0 && (x & (x - 1)) == 0; } ``` Google之时,在 [Exploring Binary](http://www.exploringbinary.com/ten-ways-to-check-if-an-integer-is-a-power-of-two-in-c/) 上面看到了作者给出了 10 种解决方案,有兴趣可以看看。从作者域名上看,他应该是探索二进制方面的专家。