leetcode 231 2 的幂

zhaojun

2023 年 01 月 20 日

929 次浏览

暂无评论

788字数

默认分类

https://leetcode.cn/problems/power-of-two/

## 题目

给你一个整数 `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`

**进阶：** 你能够不使用循环/递归解决此问题吗？

## 思路

这道题可以用位运算来解决，和 [[191. 位1的个数]] 类似，如：

2^0 = 1             0001
	2^1 = 2             0010
	2^2 = 4             0100
	2^3 = 8             1000

可以看到，如果二进制位上，一个数是 2 的幂，那么他的二进制位只会是一个。不过这里要考虑负数的情况，`-2147483648`，他的二进制位是第一个数为 1，后面的 31 个数为 0。

## 代码
```java
class Solution {
    public boolean isPowerOfTwo(int n) {
        if (n < 1) return false;

int len = 0;
        for (int i = 0; i < 32; i++) {
            if ((n & 1) == 1) {
                len++;
                if (len > 1) {
                    break;
                }
            }
            n >>= 1;
        }

return len == 1;
    }
}
```

做完题后，我去 LeetCode 官方看题解，发现有一个最优版，本质上还是判断二进制位中 1 的个数是否只有 1 个。不过这里使用了一个技巧，即 `n & (n - 1)` 可以去除 n 的二进制位中最低位的 1 转为 0。那么如果整个数字的二进制位中，只有一个 1 的话，结果就是 0，可以有了如下代码：
```java
class Solution {
    public boolean isPowerOfTwo(int n) {
        return n > 0 && (n & (n - 1)) == 0;
    }
}
```

最后修改：2023 年 01 月 20 日

如果觉得我的文章对你有用，请我喝杯咖啡吧。

leetcode 231 2 的幂

zhaojun • 2023 年 01 月 20 日

leetcode 231 2 的幂

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

谈裸辞和开源的体会

剑指 Offer 04. 二维数组中的查找

Shiro 学习 04 - 加密

通过 Github Actions 自动构建 ZFile 镜像并推送到 Docker Hub

优化 Java 项目 Docker 镜像内存占用从 500 M 到 100M

leetcode 290 单词规律

手撸 Java Web RBAC 权限管理

Shiro 学习 10 - 集成 Spring 之注解

leetcode 005 最长回文子串

一款基于 Shiro 的权限管理系统，支持 restful 风格 URL.

leetcode 231 2 的幂

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

leetcode 231 2 的幂

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款