Question
Formatted question description: https://leetcode.ca/all/342.html
342 Power of Four
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?
Algorithm
Diveded by 4
The most direct way is to keep dividing by 4 to see if the final result is 1.
Mast
First judge whether it is 2 to the Nth power: (num&(num1)) == 0
Remove the number that is not 4 to the power of N
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
The highest 1 of the power of 4 is the counting digit, then we only need to compare it with the previous number (0x55555555) <==> 1010101010101010101010101010101
. If the number obtained is still itself, we can be sure that it is a power of 4
Math
After determining that it is a power of 2, I found that as long as it is a power of 4, it can be divisible by 3 after subtracting 1.
Code
Java

public class Power_of_Four { class Solution_3 { public boolean isPowerOfFour(int num) { return num > 0 && !(num & (num  1)) && (num  1) % 3 == 0; } } class Solution_intuitive { public boolean isPowerOfFour(int num) { while (num && (num % 4 == 0)) { num /= 4; } return num == 1; } } class Solution { public boolean isPowerOfFour(int num) { return num > 0 && (num&(num1)) == 0 && (num & 0x55555555) != 0; } } }

// OJ: https://leetcode.com/problems/poweroffour/ // Time: O(1) // Space: O(1) class Solution { public: bool isPowerOfFour(int num) { return __builtin_popcount(num) == 1 && ((~0x55555555 & num) == 0); } };

class Solution(object): def isPowerOfFour(self, num): """ :type num: int :rtype: bool """ return num & (num  1) == 0 and (num  1) % 3 == 0