leetcode 231. 2的幂

题目描述:

给定一个整数,编写一个函数来判断它是否是 2 的幂次方。

示例 1:

输入: 1
输出: true
解释: 20 = 1

 思路:注意2的幂次方数有一个特点,就是化位二进制后,它只有最高位一个1。所以,可以借用之前“1的个数”的想法,把它的1的个数数出来。代码如下:

bool isPowerOfTwo(int n) {
        //不可能是2的幂次方的情况先排除
        //因为n是要-1的,负数可能引发奇怪的结果。
        if(n<=0) return false;
        int count=0;
        while(n)
        {
            count++;
            n&=n-1;
        }
        return count==1;
    }

这个应该算是O(n)的时间复杂度,测试运行时间 4ms。但其实没有必要把它所有的1都数出来。我们只需要知道,它是不是只含有一个1就行了!也就是,去掉一个1之后,它还有1吗?有的话就是false。代码如下:

bool isPowerOfTwo(int n) {
        if(n<=0) return false;
        //去掉1个1
        return n&(n-1)? false: true;
    }

O(1)的时间复杂度,应该是最简洁的办法了。不过测试运行时间还是 4ms。

 

;