LeeCode 第 342 .4的幂 Java解法

342. 4的幂

https://leetcode-cn.com/problems/power-of-four/

这题其实如果先不管进阶，还是蛮简单的，首先我们只要保证除以4余数一直为0,然后不断的把结果继续赋值到n，如果能到1，那么就是4的幂次方了。

class Solution {
    public boolean isPowerOfFour(int num) {
    if (num <= 0) {
    return false;}while (num > 1) {
    if (num % 4 != 0) {
    return false;}num = num/4;}return true;}
}

代码就是很简单了，时间复杂度就是$O(log4(n))$。

进阶

首先我们要来看看几个4的幂次方的32位二进制

00000000000000000000000000000001: 1
00000000000000000000000000000100: 4
00000000000000000000000000010000: 16
00000000000000000000000001000000: 64

我们可以看到规律：
1 就是只有一个1，以及，在奇数的位置上。
2 其次只要和偶数为上都为1且，奇数位置都是0 的相与，如果结果等于0，那么这个数字就是4的幂次方。

10101010101010101010101010101010：0xaaaaaaaa
//示例：10101010101010101010101010101010
& 00000000000000000000000000010000
----------------------------------00000000000000000000000000000000

ｓｈｏｗ　ｔｈｅ　ｃｏｄｅ

class Solution {
    public boolean isPowerOfFour(int num) {
    if((num & 0xaaaaaaaa) == 0 && Integer.bitCount(num) == 1)  {
    return true;} else {
    return false;}}
}

这个时间复杂度就是常数时间复杂度。