快速判断2的n次幂

题目

O(1)时间内检测是否为2的n次方。http://www.lintcode.com/zh-cn/problem/o1-check-power-of-2/

分析

从2的n次方很容易联想到2进制的表达形式,不妨列出来看看

2的次方十进制二进制
2011
21210
224100
2381000
241610000
...
2n2n1000...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;
    }

}
Show Comments

Get the latest posts delivered right to your inbox.