4的幂
难度:
标签:
题目描述
Given an integer n, return true if it is a power of four. Otherwise, return false.
An integer n is a power of four, if there exists an integer x such that n == 4x.
Example 1:
Input: n = 16 Output: true
Example 2:
Input: n = 5 Output: false
Example 3:
Input: n = 1 Output: true
Constraints:
-231 <= n <= 231 - 1
Follow up: Could you solve it without loops/recursion?
代码结果
运行时间: 18 ms, 内存: 15.9 MB
/*
* 题目思路：
* 判断一个整数是否为4的幂次方。
* 使用 Java 8 中的 Stream API 来实现这个功能。
* 我们可以通过二进制特性和对数计算来判断一个数是否是4的幂次方。
*/
import java.util.stream.IntStream;
public class Solution {
public boolean isPowerOfFour(int n) {
// 生成的流中只有一个符合条件的元素，返回 true
return IntStream.iterate(1, x -> x <= n, x -> x * 4)
.anyMatch(x -> x == n);
}
}
解释
方法:
该题解的思路是通过位运算来判断一个数是否为4的幂次方。首先检查该数是否大于0，然后利用 n&(n-1) 的位运算技巧判断其是否为2的幂次方。因为4的幂次方一定也是2的幂次方，但2的幂次方不一定是4的幂次方。4的幂次方的二进制表示中，只会在奇数位上有1，如 1，100，10000。所以再用 n&0x55555555 进行与运算，0x55555555 的二进制表示为 01010101010101010101010101010101，如果结果不为0，说明 n 是4的幂次方。
时间复杂度:
O(1)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么在判断4的幂次方之前需要先判断n是否大于0？
▷🦆
n&(n-1)的位运算是如何帮助判断一个数是否为2的幂次方的？
▷🦆
为什么4的幂次方的二进制表示中只会在奇数位上有1？这个规律是如何得出的？
▷