题目地址：https://leetcode.com/problems/power-of-four/open in new window
Total Accepted: 9305 Total Submissions: 28083 Difficulty: Easy
题目描述
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?
题目大意
判断一个数是不是4的幂。
解题方法
递归
如果能被4整除，就看除以4之后是否能继续整除。
class Solution(object):
def isPowerOfFour(self, num):
"""
:type num: int
:rtype: bool
"""
if num <= 0: return False
if num == 1: return True
if num % 4 == 0:
return self.isPowerOfFour(num / 4)
return False
1 2 3 4 5 6 7 8 9 10 11
AC:2ms
迭代
和递归同样的原理。
class Solution(object):
def isPowerOfFour(self, num):
"""
:type num: int
:rtype: bool
"""
if num <= 0: return False
while num % 4 == 0:
num /= 4
return num == 1
1 2 3 4 5 6 7 8 9 10
效率凑活。
位运算
查了一下，发现还有更好的方法。就是判断二进制中1出现的位数是不是在奇数位。用0101 0101 ……来进行排除。16进制数为：0x55555555。
class Solution(object):
def isPowerOfFour(self, num):
"""
:type num: int
:rtype: bool
"""
return num > 0 and (num & (num - 1)) == 0 and (num & 0x55555555) != 0
1 2 3 4 5 6 7
Java代码如下：
public class Solution {
public boolean isPowerOfFour(int num) {
return num > 0 && (num & (num - 1)) ==0 && (num & 0x55555555) !=0;
}
}
1 2 3 4 5
函数法
判断取以4为底的log之后，强转成int，再取上4的幂是不是原来的数字。
class Solution(object):
def isPowerOfFour(self, num):
"""
:type num: int
:rtype: bool
"""
return num > 0 and (4 ** (int(math.log(num, 4)))) == num
1 2 3 4 5 6 7
DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发