Description
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?
Mysolution
最low的/万能的方式的如下
class Solution {public: bool isPowerOfFour(int num) { if(num==0) return 0; while(num%4==0) num/=4; return num==1; }}; 注意到4=2**2, 已知power of 2可以用n&(n-1)的trick, power of 4就是在of 2 的基础上, 加入1存在位置的约束! 但是我并没有想出来怎么利用这个约束.. 技巧具体查看下面的discuss
Discuss
- bit trick
public class Solution { public boolean isPowerOfFour(int num) { return (num > 0) && ((num & (num - 1)) == 0) && ((num & 0x55555555) == num); }} (num & 0x55555555) == num
0x5 = ...0101
0x55 = ...0101,0101也就是5可以划分为奇偶奇偶... 通过&运算可以将偶数位置元素保留, 奇数位置抹掉(变为0),如果值不变, 就是约束了位置,如果值变化了,就是没满足这个约束.- math method
class Solution {public: bool isPowerOfFour(int num) { return ((num-1)&num)==0 && (num-1)%3==0; }}; 4^x-1=(2^x-1)(2^x+1). And 2^x mod 3 is not 0. So either 2^x-1 or 2^x +1 must be 0.
这种方式其实更难想到.但是数学证明很巧妙.