题目

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;
    }

}