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?
4^k=2^(2k) 表示成二进制即为最高为位1,后面跟着偶数个0,因此对于任意一num,我们要做的是:
1.保证它大于0.
2.如果第1条成立,验证它二进制的最高位是1,后面全是0,验证方法是:num&(num-1)=0
3.如果前两条成立,验证它后面跟着偶数个0,验证方法是:(num-1)%3=0:
第三点可以用假设检验的方法证明:
当k=1时:2^2=4 而(4-1)%3=0 成立
假设(2^(2k)-1)%3=0
则当k+1时 ,2^(2(k+1))-1=4*2^(2k)-1=3*2^(2k)+2^(2k)-1 ,加号左右两项都能被3整除,所以 k+1时假设也成立,即证得:(2^(2k)-1)%3=(4^k-1)%3=0
而如果num满足条件1和条件2,但是后面有奇数个0的时候假设num = 2^(2k+1) -1= 2*4^(k)-1=4^k+4^k-1,后项4^k-1 %3=0 前项4^k%3!=0所以后面有奇数个0 的时候(num-1)%3!=0.
代码:
class Solution(object): def isPowerOfFour(self, num): """ :type num: int :rtype: bool """ return num >0 and num&(num-1)==0 and (num-1)%3==0