这是悦乐书的第205次更新，第216篇原创
01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第72题（顺位题号是342）。给定一个整数（带符号的32位），写一个函数来检查它是否为4的幂。例如：
输入：16
输出：true
输入：5
输出：false
跟进：你可以在没有循环/递归的情况下解决它吗？
本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。
02 第一种解法
特殊情况：当num小于等于1时，直接返回num和1是否相等的结果。
正常情况：先判断对4取余是否等于0，如果等于0，则num除以4继续循环，最后判断num是否等于1。
public boolean isPowerOfFour(int num) {
if (num <= 1) {
return num == 1;
}
while (num%4 == 0) {
num /= 4;
}
return num == 1;
}
03 第二种解法
使用递归的方式，判断逻辑和第一种解法一致。
public boolean isPowerOfFour2(int num) {
if (num <= 1) {
return num == 1;
}
if (num > 1 ) {
return num%4 == 0 && isPowerOfFour2(num/4);
}
return false;
}
04 第三种解法
利用Integer.toString(int par1, int par2)方法，将num转成4进制字符串，然后匹配以1开头且尾随k(k>=0)个0的正则。
public boolean isPowerOfFour3(int num) {
return num > 0 && Integer.toString(num, 4).matches("10*");
}
05 第四种解法
将4的所有幂次方整数放入一个HashSet中，然后判断num是否被包含在其中。
public boolean isPowerOfFour4(int num) {
Set<Integer> set = new HashSet<>(Arrays.asList(1, 4, 16, 64, 256, 1024, 4096, 16384, 65536,
262144, 1048576, 4194304, 16777216, 67108864, 268435456, 1073741824));
return num > 0 && set.contains(num);
}
06 第五种解法
使用数学运算中的对数。
4^X == N
log (4^X) == log N
X log 4 == log N
X == (log N) / (log 4)
如果num是4的幂次方，那么将两数取对数后再做除法，得到的是一个以幂次方为整数位，以0位小数位的double类型数，那么对其取整再和自身做减法，那么它的绝对值肯定是无限接近于0的。
public boolean isPowerOfFour5(int num) {
double d = Math.log(num)/Math.log(4);
return Math.abs(d - Math.round(d)) <= 0.00000000001;
}
07 第六种解法
如果num是4的幂次方，那么其二进制数会满足两个条件：
-
只会有一个1。
-
后面尾随0的个数是偶数个。
第一个条件借助包装类Integer的bitCount方法，第二个条件依旧借助这个方法，但是对象变成了num-1，统计完1的位数后，对2取余，判断1的个数是否为偶数。
public boolean isPowerOfFour6(int num) {
return num > 0 && Integer.bitCount(num) == 1 && Integer.bitCount(num-1)%2 == 0;
}
08 小结
算法专题目前已连续日更超过两个月，算法题文章72+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。
以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！