1. 问题描述
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?
Tags: Bit Manipulation
Similar Problems: (E) Power of Two (E) Power of Three
2. 解题思路
判断一个数是否为4的次方数?
- 思路1：最直接的方法就是不停的除以4，看最终结果是否为1.
- 思路2：利用换底公式，参考Power of Three.
- 思路3：首先根据Power of Two中的解法二，知num & (num - 1)可用来判断一个数是否为2的次方数。然而，由于是2的次方数，不一定是4的次方数，比如8。故还要其他的限定条件，通过观察发现，4的次方数的最高位的1都是奇数位，那么只需同32位数中奇数位均为1的数(0x55555555)进行 与操作 ，若得到的数还是其本身，则可以肯定其为4的次方数：
-
- 十六进制：0x55555555
- 二进制：0101 0101 0101 0101 0101 0101 0101 0101
- 思路4：确定其是2的次方数之后，发现只要是4的次方数，减1之后可以被3整除.
3. 代码
思路1：
1 class Solution { 2 public: 3 bool isPowerOfFour_1(int num) 4 { 5 while (num && (num % 4 == 0)) 6 { 7 num /= 4; 8 } 9 return num == 1; 10 } 11 }
思路2：
1 public class Solution { 2 public boolean isPowerOfFour(int num) { 3 if(num<=0) return false; 4 return (Math.log10(num)/Math.log10(4)-(int)(Math.log10(num)/Math.log10(4)))==0; 5 } 6 }
思路3：
1 class Solution { 2 public: 3 bool isPowerOfFour_3_1(int num) 4 { 5 if(num<=0) return false; 6 return (num&(num-1))==0&&(num&0x55555555)==num; 7 } 8 9 bool isPowerOfFour_3_2(int num) 10 { 11 if(num <= 0) return false; 12 if(num & (num - 1)) return false; // 先判断是否是 2 的 N 次方 13 if(num & 0x55555555) return true; // 再将不是 4 的 N 次方的数字去掉 14 return false; 15 } 16 };
思路4：
1 class Solution { 2 public: 3 bool isPowerOfFour_4_1(int num) 4 { 5 return num > 0 && !(num & (num - 1)) && (num - 1) % 3 == 0; 6 } 7 bool isPowerOfFour_4_2(int num) 8 { 9 if(num <= 0) return false; 10 if(num & num-1) return false; 11 return num % 3 == 1; 12 } 13 };