2 的幂
难度:
标签:
题目描述
给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。
如果存在一个整数 x 使得 n == 2x ，则认为 n 是 2 的幂次方。
示例 1：
输入：n = 1 输出：true 解释：20 = 1
示例 2：
输入：n = 16 输出：true 解释：24 = 16
示例 3：
输入：n = 3 输出：false
示例 4：
输入：n = 4 输出：true
示例 5：
输入：n = 5 输出：false
提示：
-231 <= n <= 231 - 1
进阶：你能够不使用循环/递归解决此问题吗？
代码结果
运行时间: 18 ms, 内存: 16.1 MB
/*
* Problem Statement:
* Given an integer n, determine if it is a power of two.
* An integer is a power of two if there exists an integer x such that n == 2^x.
*
* Approach:
* - Using Java Streams, we can create an infinite stream of powers of two and check if n is present in that stream.
* - We limit the stream to 31 elements since 2^31 is beyond the int range.
*/
import java.util.stream.IntStream;
public class Solution {
public boolean isPowerOfTwo(int n) {
// Generate a stream of powers of two and check if n is present
return n > 0 && IntStream.iterate(1, x -> x <= Integer.MAX_VALUE / 2, x -> x * 2).anyMatch(x -> x == n);
}
}解释
方法:
这个题解的思路是利用 2 的幂次方数的二进制表示的特点。2 的幂次方数的二进制表示中只有最高位是 1，其余位都是 0。例如 2 的 0 次方 1 的二进制是 0001，2 的 1 次方 2 的二进制是 0010，2 的 2 次方 4 的二进制是 0100，依此类推。所以我们可以不断地将输入的数 n 除以 2，如果 n 是 2 的幂次方数，最终 n 会等于 1。同时在除以 2 的过程中，如果出现了余数不等于 0 的情况，说明 n 不是 2 的幂次方数，可以提前返回 false。
时间复杂度:
O(log n)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么在算法中，一开始要检查`n`是否为0？
▷🦆
在代码中，使用`while not n%2`循环来不断除以2，是否考虑过对负数`n`的处理？
▷🦆
为什么在循环结束后，直接检查`n==1`来确定是否是2的幂次方，是否能处理所有情况？
▷🦆
在不使用循环/递归的情况下，有哪些其他方法可以判断一个数是否是2的幂次方？
▷相关问题
位1的个数
编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '1' 的个数（也被称为汉明重量）。
提示：
- 请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
- 在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在 示例 3 中，输入表示有符号整数
-3。
示例 1：
输入：n = 00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。
示例 2：
输入：n = 00000000000000000000000010000000 输出：1 解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。
示例 3：
输入：n = 11111111111111111111111111111101 输出：31 解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。
提示：
- 输入必须是长度为
32的 二进制串 。
进阶：
- 如果多次调用这个函数，你将如何优化你的算法？