运用 lowbit 判断 2 的幂

简介: 运用 lowbit 判断 2 的幂

网络异常,图片无法展示
|

题目描述



这是 LeetCode 上的 231. 2 的幂 ,难度为 简单


Tag : 「数学」、「位运算」


给你一个整数 n,请你判断该整数是否是 2 的幂次方。如果是,返回 true ;否则,返回 false 。


如果存在一个整数 x 使得 n == 2^x2x ,则认为 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
复制代码


提示:


  • -2^{31}231 <= n <= 2^{31}231 - 1


进阶:你能够不使用循环/递归解决此问题吗?


朴素做法



首先小于等于 00 的数必然不是,11 必然是。


在处理完这些边界之后,尝试将 nn 除干净,如果最后剩余数值为 11 则说明开始是 22 的幂。


代码:


class Solution {
    public boolean isPowerOfTwo(int n) {
        if (n <= 0) return false;
        while (n % 2 == 0) n /= 2;
        return n == 1;
    }
}
复制代码


  • 时间复杂度:O(\log{n})O(logn)
  • 空间复杂度:O(1)O(1)


lowbit



熟悉树状数组的同学都知道,lowbit 可以快速求得 x 二进制表示中最低位 1 表示的值。


如果一个数 nn22 的幂,那么有 lowbit(n) = n 的性质(22 的幂的二进制表示中必然是最高位为 11,低位为 00)。


代码:


class Solution {
    public boolean isPowerOfTwo(int n) {
        return n > 0 && (n & -n) == n;
    }
}
复制代码


  • 时间复杂度:O(1)O(1)
  • 空间复杂度:O(1)O(1)


最后



这是我们「刷穿 LeetCode」系列文章的第 No.231 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先将所有不带锁的题目刷完。


在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。


为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:github.com/SharingSour…


在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

相关文章
|
存储 监控 Shell
【Shell 命令集合 文件传输 】Linux ftpcount 命令使用指南
【Shell 命令集合 文件传输 】Linux ftpcount 命令使用指南
191 0
|
9月前
|
搜索推荐 算法 大数据
大数据无处不在:揭秘日常生活中的大数据魔力
大数据无处不在:揭秘日常生活中的大数据魔力
383 10
|
11月前
|
程序员 Go
go语言中if 语句
go语言中if 语句
187 3
|
11月前
|
存储 安全 大数据
大数据水平分区增强可管理性
【11月更文挑战第2天】
147 5
|
10月前
|
数据挖掘 大数据 数据处理
python--列表list切分(超详细)
通过这些思维导图和分析说明表,您可以更直观地理解Python列表切分的概念、用法和实际应用。希望本文能帮助您更高效地使用Python进行数据处理和分析。
620 10
|
存储 并行计算 测试技术
NumPy 性能优化:提升 Python 数值计算的速度
【8月更文第30天】Python 是一种广泛使用的编程语言,在科学计算领域尤其受欢迎。然而,由于 Python 的动态类型和解释执行机制,其在处理大规模数值数据时可能会显得相对较慢。为了克服这一限制,NumPy(Numerical Python)库提供了高性能的多维数组对象以及一系列用于操作这些数组的函数。本文将探讨如何利用 NumPy 来提高 Python 中数值运算的效率。
1146 1
|
监控 JavaScript 前端开发
深入理解与实践:利用监听事件优化应用程序响应性
【7月更文挑战第3天】事件监听是软件开发中的关键,基于“发布-订阅”模式,用于响应用户操作、系统变化等。常见于UI交互、异步编程、系统事件和游戏开发。JavaScript示例展示了如何监听按钮点击:添加事件监听器到元素,定义处理函数。进阶技巧包括事件委托、冒泡与捕获、节流和防抖,用于优化性能和用户体验。理解并运用事件监听能提升应用质量。
474 2
|
数据可视化 黑灰产治理
📊 ECharts 雷达图案例002 - 诈骗性质分析
**ECharts 案例展示了诈骗性质的雷达图分析,以创新可视化揭示诈骗模式。定制化雷达图配色鲜明,多维度剖析不同诈骗手段,如网络刷单、冒充公检法。交互式设计允许用户深入探究细节。[点击这里](https://download.csdn.net/download/No_Name_Cao_Ni_Mei/89454384)查看完整案例。#ECharts #数据可视化 #雷达图 #诈骗分析**
173 0
📊 ECharts 雷达图案例002 - 诈骗性质分析
|
Java uml
UML之组件图(构件图)
UML之组件图(构件图)
753 0
|
JSON JavaScript 前端开发
TypeScript笔记(2)—— 使用VSCode实时编译TypeScript代码
TypeScript笔记(2)—— 使用VSCode实时编译TypeScript代码
624 0