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?
M1: loop
time = O(log_4(n)), space = O(1)
class Solution { public boolean isPowerOfFour(int num) { if(num < 1) { return false; } while(num % 4 == 0) { num /= 4; } return num == 1; } }
M2: 换底公式
time = unknown, space = O(1)
class Solution { public boolean isPowerOfFour(int num) { return (Math.log10(num) / Math.log10(4)) % 1 == 0; } }
M3: bit manipulation
n > 0 and (num & (num - 1)) == 0 makes sure num is a power of 2
0x55555555 == 1010101010101010101010101010101 in binary with a length of 32, (num & 0x55555555) != 0 makes sure the 1 locates in the odd location
time = O(1), space = O(1)
class Solution { public boolean isPowerOfFour(int num) { return num > 0 && (num & (num - 1)) == 0 && (num & 0x55555555) != 0; } }
原文：https://www.cnblogs.com/fatttcat/p/11400716.html