PowerOfFour [source code]

public class PowerOfFour {
static

public class Solution {
    public boolean isPowerOfFour(int num) {
        if (num <= 0) return false;
        else if (num == 1) return true;
        while (num != 1 && num > 0 && (num & (num - 1)) == 0) {
            num = num >>> 2;
        }
        return num == 1;
    }
}

    public static void main(String[] args) {
        PowerOfFour.Solution tester = new PowerOfFour.Solution();
        assert tester.isPowerOfFour(1) == true;
        assert tester.isPowerOfFour(4) == true;
        assert tester.isPowerOfFour(16) == true;
        assert tester.isPowerOfFour(64) == true;
        assert tester.isPowerOfFour(2) == false;
        assert tester.isPowerOfFour(8) == false;
        assert tester.isPowerOfFour(15) == false;
        // System.out.println(tester.isPowerOfFour(Integer.parseInt(args[0])));
    }
}

刚开始也就是想写一个 naive 的解法, 也写了半天, 最后的速度还不怎么样:2(24).

一开始的想法很蠢, 认为只要 num 是 powerOf2, 然后 num/2之后还是 powerOf2就行了. 都不知道当时脑子怎么想的.

然后自己写几个 bit 来看看规律, 注意的是你的逻辑要有一个区分的对象, 这里有三种:

  1. 16这样的PowerOf4;
  2. 8这样的不是 PowerOf4,但是是 PowerOf2;
  3. 15这样不是 PowerOf2的;

另外这题的 followup 估计还是用穷举? 最大的 PowerOf2是2^30, 那么最大的 PowerOf4就是4^15, 也就是总共只有16个数字, 穷举很简单.

这个是 submission 看到的另外一个写法: 

public class Solution {  
    public boolean isPowerOfFour(int num) {  
        return (num > 0) && ((num&(num-1))==0) && ((num & 0x55555555) == num);  
    }  
}

理解这个算法, 还是用逻辑链思路: 当第一项和第二项判断成功之后, 剩下的就全是 PowerOf2了. 下面我们要排除类似8的. 做法就是用&完成一个 filter 的功能(&的功能就是一个按位置准入), 换一个说法 ,如果这个leading 0出现在奇数位置, 才能通过第三项.
另一个类似的写法: 

public boolean isPowerOfFour(int num) {  
    return num > 0 && (num&(num-1)) == 0 && (num & 0x55555555) != 0;  
    //0x55555555 is to get rid of those power of 2 but not power of 4  
    //so that the single 1 bit always appears at the odd position   
}

这里的 != 0 跟上面的 ==num 其实是一样的, 因为 num 里面反正就只有一个1;

这个是另外一个思路: 

bool isPowerOfFour(int num) {  
    return num > 0 && (num & (num - 1)) == 0 && (num - 1) % 3 == 0;  
}

这个思路的证明方法有很多:

  1. (4^n-1) = (4-1) (4^(n-1) + 4^(n-2) + 4^(n-3) + ..... + 4 + 1)
  2. (by induction) 4^(n+1) - 1 = 44^n -1 = 34^n + 4^n-1. The first is divided by 3, the second is proven by induction hypothesis
  3. 4^n - 1 = (2^n + 1) * (2^n - 1). among any 3 consecutive numbers, there must be one that is a multiple of 3
    among (2^n-1), (2^n), (2^n+1), one of them must be a multiple of 3, and (2^n) cannot be the one, therefore either (2^n-1) or (2^n+1) must be a multiple of 3, and 4^n-1 must be a multiple of 3 as well.
  4. (3 + 1) ^ n (n >= 0) has multiple components that all has 3 as one of factors except the trailing 1. That's why all number which is power of four have residual as 1 when they modulo 3. (级数的观点)
  5. Denote a number with m of "1" in serial in the end as "serial1(m)".
    we have:
    serial1(2k) == 4^k-1 == 3 + (3<<2) + (3<<4) +...+ (3<<(2(k-1))) == 3(4^0) + 3(4^1) + 3(4^2) +...+ 3(4^(k-1));
    so (4^k-1)%3==0 for any k.
    While for those that are a power of 2 but not a power of 4, we have:
    serial1(2k+1) == 2^(2k+1)-1 == 3 + (3<<2) + (3<<4) +...+ (3<<(2    (k-1))) + (1<<2k) == 3(4^0) + 3(4^1) + 3(4^2) +...+ 3(4^(k-1)) + (1<<2k);
    So serial1(2k+1)%3 !=0 for all k;

这里2和5两个证法按理是应该可以想的出来的; 另外, leetcode 上面真是藏龙卧虎;

这个 regex 的做法还是可以的: 

public boolean isPowerOfFour(int num) {  
    return Integer.toString(num, 4).matches("10*");  
}

严格来说这个做法通用于所有的 power 题;

Problem Description

Given an integer (signed 32 bits), write a function to check whether it is a power of 4.

Example:
Given num = 16, return true. Given num = 5, return false.

Follow up: Could you solve it without loops/recursion?

Credits:
Special thanks to @yukuairoy for adding this problem and creating all test cases.

Difficulty:Easy
Category:Algorithms
Acceptance:38.29%
Contributor: LeetCode
Companies
two sigma
Related Topics
bit manipulation
Similar Questions
Power of Two Power of Three

results matching ""

    No results matching ""