Power of Four (E)

题目

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

Example 1:

Input: 16
Output: true

Example 2:

Input: 5
Output: false

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


题意

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

思路

  1. 循环判断余数;

  2. 直接求对数再进行判断;

  3. 找规律:

    首先,(4^{k+1})相当于将(4^k)的二进制向左移动两位,初始从1开始,所以4的幂次方的二进制表示中一定只有一个1;

    其次,因为每次向左移动两位,这个1后面一定跟着偶数个0,1一定出现在从右向左第奇数个位置上,只要将num和((0101)_2)相与,只要结果不为0,那么这个1一定出现在奇数为上。


代码实现

Java

循环

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

对数

class Solution {
    public boolean isPowerOfFour(int num) {
        double n = Math.log(num) / Math.log(4);
        return n == ((int) n) * 1.0;
    }
}

找规律

class Solution {
    public boolean isPowerOfFour(int num) {
        return ((num & (num - 1)) == 0) && ((num & 0x55555555) != 0);
    }
}
内容来源于网络如有侵权请私信删除