Leetcode_342_Power of Four

http://blog.csdn.net/pistolove/article/details/52198328

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.  Subscribe to see which companies asked this question 

思路：

（1）该题为给定一个整数，判断该整数是否为4的次方数。

（2）该题属于简单题。用一个循环进行判断即可得到结果。由于用循环比较简单，这里不再累赘。下文简单阐述两种非循环的实现方式，都是基于2的次方数实现的，感兴趣可以看看。

（3）算法代码实现如下，希望对你有所帮助。

package leetcode;

public class Power_of_Four {

    public static boolean isPowerOfFour(int num) {
        if (num <= 0)
            return false;

        if (num == 1)
            return true;

        while (true) {
            if (num % 4 == 0) {
                num = num / 4;
                if (num == 1)
                    return true;
            } else {
                return false;
            }
        }
    }

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21

网上的一些其它算法实现：

（1）如果该整数是2的次方数，只要是4的次方数，减1之后可以被3整除，则说明该整数是4的次方数，见下方代码：

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

• 1
• 2
• 3
• 4
• 5
• 1
• 2
• 3
• 4
• 5

（2）2的次方数在二进制下只有最高位是1，但不一定是4的次方数，观察发现4的次方数的最高位的1都是计数位，只需与上0x55555555（等价 1010101010101010101010101010101），如果得到的数还是其本身，则可以肯定其为4的次方数，见下方代码：

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

• 1
• 2
• 3
• 4
• 5
• 1
• 2
• 3
• 4
• 5