数字范围按位与
优质博文:IT-BLOG-CN
题目
给你两个整数left
和right
,表示区间[left, right]
,返回此区间内所有数字 按位与 的结果(包含left
、right
端点)。
示例 1:
输入:left = 5, right = 7
输出:4
示例 2:
输入:left = 0, right = 0
输出:0
示例 3:
输入:left = 1, right = 2147483647
输出:0
0 <= left <= right <= 231 - 1
代码
最直观的解决方案就是迭代范围内的每个数字,依次执行按位与运算,得到最终的结果,但此方法在 [m,n] 范围较大的测试用例中会因超出时间限制而无法通过,因此我们需要另寻他路。
我们观察按位与运算的性质。对于一系列的位,例如 [1,1,0,1,1],只要有一个零值的位,那么这一系列位的按位与运算结果都将为零。
回到本题,首先我们可以对范围内的每个数字用二进制的字符串表示,例如 9=00001001(2) ,然后我们将每个二进制字符串的位置对齐。
在上图的例子中,我们可以发现,对所有数字执行按位与运算的结果是所有对应二进制字符串的公共前缀再用零补上后面的剩余位。
那么这个规律是否正确呢?我们可以进行简单的证明。假设对于所有这些二进制串,前 i 位均相同,第 i+1 位开始不同,由于 [m,n] 连续,所以第 i+1 位在 [m,n] 的数字范围从小到大列举出来一定是前面全部是 0,后面全部是 1,在上图中对应 [9,11] 均为 0,[12,12] 均为 1。并且一定存在连续的两个数 x 和 x+1,满足 x 的第 i+1 位为 0,后面全为 1,x+1 的第 i+1 位为 1,后面全为 0,对应上图中的例子即为 11 和 12。这种形如 0111… 和 1000… 的二进制串的按位与的结果一定为 0000…,因此第 i+1 位开始的剩余位均为 0,前 i 位由于均相同,因此按位与结果不变。最后的答案即为二进制字符串的公共前缀再用零补上后面的剩余位。
进一步来说,所有这些二进制字符串的公共前缀也即指定范围的起始和结束数字 m 和 n 的公共前缀(即在上面的示例中分别为 9 和 12)。
因此,最终我们可以将问题重新表述为:给定两个整数,我们要找到它们对应的二进制字符串的公共前缀。
方法一:位移
思路
鉴于上述问题的陈述,我们的目的是求出两个给定数字的二进制字符串的公共前缀,这里给出的第一个方法是采用位移操作。
我们的想法是将两个数字不断向右移动,直到数字相等,即数字被缩减为它们的公共前缀。然后,通过将公共前缀向左移动,将零添加到公共前缀的右边以获得最终结果。
算法
如上述所说,算法由两个步骤组成:
我们通过右移,将两个数字压缩为它们的公共前缀。在迭代过程中,我们计算执行的右移操作数。
将得到的公共前缀左移相同的操作数得到结果。
class Solution {public int rangeBitwiseAnd(int m, int n) {int shift = 0;// 找到公共前缀while (m < n) {m >>= 1;n >>= 1;++shift;}return m << shift;}
}
时间复杂度: O(logn)。算法的时间复杂度取决于 m 和 n 的二进制位数,由于 m≤n,因此时间复杂度取决于 n 的二进制位数。
空间复杂度: O(1)。我们只需要常数空间存放若干变量。
方法二:Brian Kernighan 算法
思路与算法
还有一个位移相关的算法叫做「Brian Kernighan 算法」,它用于清除二进制串中最右边的 1。
Brian Kernighan 算法的关键在于我们每次对 number 和 number−1 之间进行按位与运算后,number 中最右边的 1 会被抹去变成 0。
基于上述技巧,我们可以用它来计算两个二进制字符串的公共前缀。
其思想是,对于给定的范围 [m,n](m<n),我们可以对数字 n 迭代地应用上述技巧,清除最右边的 1,直到它小于或等于 m,此时非公共前缀部分的 1 均被消去。因此最后我们返回 n 即可。
在上图所示的示例(m=9,n=12)中,公共前缀是 00001。在对数字 n 应用 Brian Kernighan 算法后,后面三位都将变为零,最后我们返回 n 即可。
class Solution {public int rangeBitwiseAnd(int m, int n) {while (m < n) {// 抹去最右边的 1n = n & (n - 1);}return n;}
}
时间复杂度: O(logn)。和位移方法类似,算法的时间复杂度取决于 m 和 n 二进制展开的位数。尽管和位移方法具有相同的渐近复杂度,但 Brian Kernighan 的算法需要的迭代次数会更少,因为它跳过了两个数字之间的所有零位。
空间复杂度: O(1)。我们只需要常数空间存放若干变量。
相关文章:

数字范围按位与
优质博文:IT-BLOG-CN 题目 给你两个整数left和right,表示区间[left, right],返回此区间内所有数字 按位与 的结果(包含left、right端点)。 示例 1: 输入:left 5, right 7 输出:…...

WebRTC编译后替换libwebrtc.aar时提示找不到libjingle_peerconnection_so.so库
Loading native library: jingle_peerconnection_so 问题原因:编译的时候只编译了armeabi-v7a的版本,但是应用程序是arm64-v8a,所以无法运行 解决方法:更新编译脚本,加上arm64-v8a进行编译 ./tools_webrtc/android/bu…...

Nature Electronics |无感佩戴的纤维基电子皮肤(柔性半导体器件/柔性健康监测/电子皮肤/柔性传感/纤维器件)
英国剑桥大学Yan Yan Shery Huang课题组,在《Nature Electronics 》上发布了一篇题为“Imperceptible augmentation of living systems with organic bioelectronic fibres”的论文,第一作者为王文宇博士(Wenyu Wang),论文内容如下: 一、 摘要 利用电子技术对人类皮肤和…...

深入剖析Docker容器安全:挑战与应对策略
随着容器技术的广泛应用,Docker已成为现代应用开发和部署的核心工具。它通过轻量级虚拟化技术实现应用的隔离与封装,提高了资源利用率。然而,随着Docker的流行,其安全问题也成为关注焦点。容器化技术虽然提供了良好的资源隔离&…...

后端技术打怪升级之路
记录后端技术打怪升级之路,如下是个人总记的主要技术栈,仅供参考! 备注: 同名文章一同步发表于个人网站及微信公众号 个人网站 工藤新一的技术小窝...
Leetcode 3296. Minimum Number of Seconds to Make Mountain Height Zero
Leetcode 3296. Minimum Number of Seconds to Make Mountain Height Zero 1. 解题思路2. 代码实现 题目链接:3296. Minimum Number of Seconds to Make Mountain Height Zero 1. 解题思路 这一题的思路的话我们采用的是一个二分法的思路,找到一个最大…...

计算机毕业设计之:基于深度学习的路面检测系统(源码+部署文档+讲解)
博主介绍: ✌我是阿龙,一名专注于Java技术领域的程序员,全网拥有10W粉丝。作为CSDN特邀作者、博客专家、新星计划导师,我在计算机毕业设计开发方面积累了丰富的经验。同时,我也是掘金、华为云、阿里云、InfoQ等平台…...
测试面试题:接口自动化测试流程?
1、测试用例编写:根据接口的需求和功能,编写相应的测试用例。测试用例应包括正常、边界和异常等各种情况下的测试。 2、准备测试数据:根据测试用例的要求,准备相应的测试数据。数据可以通过手动输入、数据库查询、文件导入等方式进…...
Golang面试题
在Golang(也称为Go语言)工程师的面试中,可能会遇到各种技术性和概念性的问题。 一、基础部分 Golang 中 make 和 new 的区别? 共同点:两者都用于分配内存。不同点: make 专为 slice、map 和 channel 设计,返回初始化后的(非零)值。new 分配内存并返回指向该内存的指针…...

《飞机大战游戏》实训项目(Java GUI实现)(设计模式)(简易)
目录 一、最终实现后,效果如下。 (1)简单介绍本游戏项目(待完善) (2)运行效果图(具体大家自己可以试) 初始运行情况。 手动更换背景图。 通过子弹攻击敌机,累…...

计算机毕业设计 基于 Hadoop平台的岗位推荐系统 SpringBoot+Vue 前后端分离 附源码 讲解 文档
🍊作者:计算机编程-吉哥 🍊简介:专业从事JavaWeb程序开发,微信小程序开发,定制化项目、 源码、代码讲解、文档撰写、ppt制作。做自己喜欢的事,生活就是快乐的。 🍊心愿:点…...

【数据结构与算法】LeetCode:二分查找
文章目录 二分查找二分查找搜索插入位置 (Hot 100)x 的平方根搜索二维矩阵(Hot 100)在排序数组中查找元素的第一个和最后一个位置 (Hot 100)搜索旋转排序数组 (Hot 100)寻找旋转排序…...
专题·大模型安全 | 生成式人工智能的内容安全风险与应对策略
正如一枚硬币的两面,生成式人工智能大模型(以下简称“生成式大模型”)在助力内容生成的同时也潜藏风险,成为虚假信息传播、数据隐私泄露等问题的温床,加剧了认知域风险。与传统人工智能(AI)相比…...
CORS跨域+Nginx配置、Apache配置
CORS(Cross-Origin Resource Sharing,跨源资源共享)是一种机制,它使用额外的HTTP头部来告诉浏览器允许一个网页运行的脚本从不同于它自身来源的服务器上请求资源(例如字体、JavaScript、CSS等)。这是一种安…...

文件查找和打包压缩【1.7】
文件查找和打包压缩【1.7】 八、文件查找和打包压缩8.1 文件查找8.1.1 locate8.1.2 findfind8.1.2.1 指定搜索目录层级8.1.2.2 先处理文件再处理目录8.1.2.3 根据文件名和inode查找8.1.2.4 根据属主属组查找8.1.2.5 根据文件类型查找8.1.2.6 空文件或目录8.1.2.7 组合条件8.1.2…...
速盾:cdn一般多长时间清理下缓存?
CDN(Content Delivery Network)是一种网络加速技术,通过将网站的静态资源(如图片、视频、CSS、JavaScript等)分布到全球各地的服务器节点上,从而提高用户访问这些资源的速度和体验。CDN还具备缓存功能&…...

react hooks--useRef
基本用法 在类组件中获取一个dom元素实例,可以通过React.CreateRef或者回调函数的方式去获取。语法:const refContainer useRef(initialValue);使用场景:在 React 中进行 DOM 操作时,用来获取 DOM作用:返回一个带有 …...
GPT对话知识库——将寄存器中的一位数据读到变量中需要什么步骤?C语言中掩码的作用。
目录 1,问: 1,答: 1. 确定目标寄存器地址 2. 定位目标位 位操作的基本步骤: 3. 示例代码 示例步骤: 4. 详细解释步骤 5. 举例 6. 常见用法 总结 注: C语言中掩码的作用:…...
【计算机网络】运输层协议解析
前言 运输层直接为应用进程间的逻辑通信提供服务。运输层向高层用户屏蔽了下面网络核心细节(如网络拓扑、路由选择协议等)它使应用进程看见的就好像是在两个运输层实体之间有一条端到端的逻辑通信信道。 UDP与TCP对比 UDP: 无连接 支持一对…...

Redis存储原理
前言 我们从redis服务谈起,redis是单reactor,命令在redis-server线程处理。还有若干读写IO线程负责IO操作(redis6.0之后,Redis之pipeline与事务)。此外还有一个内存池线程负责内存管理、一个后台文件线程负责大文件的关…...
大语言模型如何处理长文本?常用文本分割技术详解
为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...
Matlab | matlab常用命令总结
常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...

【论文阅读28】-CNN-BiLSTM-Attention-(2024)
本文把滑坡位移序列拆开、筛优质因子,再用 CNN-BiLSTM-Attention 来动态预测每个子序列,最后重构出总位移,预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵(S…...
什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南
文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果
Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)
目录 一、👋🏻前言 二、😈sinx波动的基本原理 三、😈波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、🌊波动优化…...

【C++特殊工具与技术】优化内存分配(一):C++中的内存分配
目录 一、C 内存的基本概念 1.1 内存的物理与逻辑结构 1.2 C 程序的内存区域划分 二、栈内存分配 2.1 栈内存的特点 2.2 栈内存分配示例 三、堆内存分配 3.1 new和delete操作符 4.2 内存泄漏与悬空指针问题 4.3 new和delete的重载 四、智能指针…...

基于Java+VUE+MariaDB实现(Web)仿小米商城
仿小米商城 环境安装 nodejs maven JDK11 运行 mvn clean install -DskipTestscd adminmvn spring-boot:runcd ../webmvn spring-boot:runcd ../xiaomi-store-admin-vuenpm installnpm run servecd ../xiaomi-store-vuenpm installnpm run serve 注意:运行前…...
C语言中提供的第三方库之哈希表实现
一. 简介 前面一篇文章简单学习了C语言中第三方库(uthash库)提供对哈希表的操作,文章如下: C语言中提供的第三方库uthash常用接口-CSDN博客 本文简单学习一下第三方库 uthash库对哈希表的操作。 二. uthash库哈希表操作示例 u…...

c++第七天 继承与派生2
这一篇文章主要内容是 派生类构造函数与析构函数 在派生类中重写基类成员 以及多继承 第一部分:派生类构造函数与析构函数 当创建一个派生类对象时,基类成员是如何初始化的? 1.当派生类对象创建的时候,基类成员的初始化顺序 …...
提升移动端网页调试效率:WebDebugX 与常见工具组合实践
在日常移动端开发中,网页调试始终是一个高频但又极具挑战的环节。尤其在面对 iOS 与 Android 的混合技术栈、各种设备差异化行为时,开发者迫切需要一套高效、可靠且跨平台的调试方案。过去,我们或多或少使用过 Chrome DevTools、Remote Debug…...