题目
O(1)时间内检测是否为2的n次方。http://www.lintcode.com/zh-cn/problem/o1-check-power-of-2/
分析
从2的n次方很容易联想到2进制的表达形式,不妨列出来看看
2的次方 | 十进制 | 二进制 |
---|---|---|
20 | 1 | 1 |
21 | 2 | 10 |
22 | 4 | 100 |
23 | 8 | 1000 |
24 | 16 | 10000 |
... | ||
2n | 2n | 1000...0 |
透过上表可以发现,任何一个2的n次方数,转化成二进制表示后,最高位是1,其余位都是0,否则这个数就不是2的次方。如何快速的判断给定的数x转化成二进制后是否满足1000...00这种模式呢?有一个非常巧妙的办法,因为x-1=111...1,比x少一个比特位,而同时除了最高位之外,其他位的值都是1,而x-1的最高位又可以认为是0,因此,当x & (x-1) == 0时,x必然是2的n次幂,否则,x必不为2的n次幂。
代码
public class Solution {
/*
* @param n: An integer
* @return: True or false
*/
public boolean checkPowerOf2(int n) {
// write your code here
if( n < 1) return false;
return (n&(n-1)) == 0;
}
}