Tips判断一个数是不是4的幂次方

35次阅读

共计 544 个字符,预计需要花费 2 分钟才能阅读完成。

久违的双百,QAQ
Leetcode-342

题目上说了尽量不要使用循环或者递归,于是想到了之前做过的判断一个数是不是 2 的幂次方,因此,我们看一哈有没有相似性。

4 的幂次方一定是 2 的幂次方,但是反过来却不成立。例如,8 是 2 的 3 次方,但并不是 4 的幂次方。

1 转成 2 进制是 1;
4 转成 2 进制是 100;
6 转成 2 进制是 110;
8 转成 2 进制是 1000;
16 转成 2 进制是 10000;

判断一个数是不是 2 的幂次方,我们要看这个数转成 2 进制后是不是所有位数只有 1 个 1。
那 4 的幂次方的规律就是看这个数转成 2 进制后是不是所有位数只有 1 个 1,并且这个 1 只能在奇数位上出现。

code:

class Solution {
public:
    bool isPowerOfFour(int num) {if(num == 1) return true;
        if(num <= 3) return false;
        int count = 0;
        int i = 1;
        while(num != 0){if((num&1) != 0 && (i&1) != 0){count++;}
            if((i&1) == 0 && (num&1) != 0){return false;}
            num>>=1;
            i++;
        }
        if(count == 1)
        return true;
        return false;
    }
};

这样子的解决方法相较于循环等方法肯定是省力不少的。

正文完
 0