LeetCode 231 Power of Two 题解

题意

给一个整数,判断这个数是否是2的整数次方。

分析

这个题目非常简单,32位整数范围内2的整数次方也就32个数,一个一个判断都可以。而一个比较好的策略是利用位运算。我们知道2的整数次方的二进制一定是在某个位只有一个1,而其他位均为0. 例如:

  • $2^0 = (1)_{10} = (1)_{2}$
  • $2^1 = (2)_{10} = (10)_{2}$
  • $2^2 = (4)_{10} = (100)_{2}$
  • $2^3 = (6)_{10} = (1000)_{2}$
  • $2^4 = (8)_{10} = (10000)_{2}$
  • ……

有一个经典的位运算,(n & (n - 1)),其作用是将一个数的二进制中最低位的一个1变成0. 而其中n - 1的作用是将最低的为1的位的右边(低位方向)所有位都变成1,而之前最低的那个1变成0. 例如$(01001000)_2$,减一之后是$(01000111)_2$。而这个数再与原数进行与运算,其结果就是最低位的1变成了0.

在这道题中,如果原数是2的整数次方,则整个数中只有一个1,消掉最低位的1就意味着整个数就变成了0. 这就可以证明原数是2的整数次方,而如果原数不是2的整数次方,则二进制中不止一个1,消掉最后一个1原数也不为0. 代码很简单,只有1行。

C代码:

1
2
3
bool isPowerOfTwo(int n) {
return n > 0 && !((n - 1) & n);
}

需要注意的是,评测数据中有0和负数,所有要多判断一下n大于0. 另外,这个位运算还可以用来解Leetcode上的191题:Number of 1 Bits,这道题更简单粗暴,直接要求统计1的个数。


版权声明

The Bloom of Youth by KUANG Qi is licensed under a Creative Commons BY-NC-ND 4.0 International License.
况琪创作并维护的锦瑟华年博客采用创作共用保留署名-非商业-禁止演绎4.0国际许可证

本文首发于The Bloom of Youth | 锦瑟华年博客( http://kuangqi.me ),版权所有,侵权必究。

本文永久链接:http://kuangqi.me/programming/leetcode-power-of-two/