[LeetCode] 231. Power of Two

链接:231. Power of Two

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

举例:20=1, 21=2, 22=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
...     .... ....

所以,算法就已经浮现了:

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

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

发表于:2015年09月21日 ,阅读量:613 ,标签:算法 · LeetCode · 位运算

版权声明:若非特别注明,本站所有文章均为作者原创,转载请务必注明原文地址。