2的幂
2021/9/11 23:05:15
本文主要是介绍2的幂,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
这道题出自LeetCode,题目如下:
给你一个整数 n
,请你判断该整数是否是 2 的幂次方。如果是,返回 true
;否则,返回 false
。
如果存在一个整数 x
使得 n == \(2^x\) ,则认为 n
是 2 的幂次方。
示例 1:
输入:n = 1
输出:true
解释:\(2^0\) = 1
示例 2:
输入:n = 16
输出:true
解释:\(2^4\) = 16
示例 3:
输入:n = 3
输出:false
示例 4:
输入:n = 4
输出:true
示例 5:
输入:n = 5
输出:false
这道题有3种比较trick的解法。首先,如果一个整数它是2的幂次方,那么它的二进制表示必然为:
\[n = 1 \underbrace{0...0}_{k} \]也就是它只有一个二进制位为1。那么问题显然可以转换为计算n的二进制位为1的数量,我们这里只需要判断是否数量为1即可,也就是去计算n & (n - 1)的值是否为0即可:
\[n = 1 \underbrace{0...0}_{k} \\ n - 1 = 0 \underbrace{1...1}_{k} \\ \]class Solution { public: bool isPowerOfTwo(int n) { return n > 0 && (n & (n - 1)) == 0; } };
第二种解法是计算n的最低二进制位为1的数是否与n相等。如果相等,说明n只有一个二进制位为1。计算n的最低二进制位为1的数的方法是去计算n & (-n)的值:
\[n = 1 \underbrace{0...0}_{k} \\ -n = 0 \underbrace{1..1}_k + 1 = 1 \underbrace{0...0}_{k} \]class Solution { public: bool isPowerOfTwo(int n) { return n > 0 && (n & -n) == n; } };
最后还有一种比较取巧的做法,就是我们已知最大的2的幂的值为\(2^{30}=1073741824\),那么只要判断n是否为其约数即可:
class Solution { private: static constexpr int BIG = 1 << 30; public: bool isPowerOfTwo(int n) { return n > 0 && BIG % n == 0; } };
这篇关于2的幂的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-01为什么公共事业机构会偏爱 TiDB :TiDB 数据库在某省妇幼健康管理系统的应用
- 2024-04-26敏捷开发:想要快速交付就必须舍弃产品质量?
- 2024-04-26静态代码分析的这些好处,我竟然都不知道?
- 2024-04-26你在测试金字塔的哪一层?(下)
- 2024-04-26快刀斩乱麻,DevOps让代码评审也自动起来
- 2024-04-262024年最好用的10款ER图神器!
- 2024-04-2203-为啥大模型LLM还没能完全替代你?
- 2024-04-2101-大语言模型发展
- 2024-04-17基于SpringWeb MultipartFile文件上传、下载功能
- 2024-04-14个人开发者,Spring Boot 项目如何部署