数字范围按位与
优质博文: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、自我改进型人工智能的崛起2、人工智能如何挑战人类监管?3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...
R语言AI模型部署方案:精准离线运行详解
R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...

《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》
在注意力分散、内容高度同质化的时代,情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现,消费者对内容的“有感”程度,正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中࿰…...
C++中string流知识详解和示例
一、概览与类体系 C 提供三种基于内存字符串的流,定义在 <sstream> 中: std::istringstream:输入流,从已有字符串中读取并解析。std::ostringstream:输出流,向内部缓冲区写入内容,最终取…...
拉力测试cuda pytorch 把 4070显卡拉满
import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试,通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小,增大可提高计算复杂度duration: 测试持续时间(秒&…...

初学 pytest 记录
安装 pip install pytest用例可以是函数也可以是类中的方法 def test_func():print()class TestAdd: # def __init__(self): 在 pytest 中不可以使用__init__方法 # self.cc 12345 pytest.mark.api def test_str(self):res add(1, 2)assert res 12def test_int(self):r…...

ubuntu22.04有线网络无法连接,图标也没了
今天突然无法有线网络无法连接任何设备,并且图标都没了 错误案例 往上一顿搜索,试了很多博客都不行,比如 Ubuntu22.04右上角网络图标消失 最后解决的办法 下载网卡驱动,重新安装 操作步骤 查看自己网卡的型号 lspci | gre…...
k8s从入门到放弃之Pod的容器探针检测
k8s从入门到放弃之Pod的容器探针检测 在Kubernetes(简称K8s)中,容器探测是指kubelet对容器执行定期诊断的过程,以确保容器中的应用程序处于预期的状态。这些探测是保障应用健康和高可用性的重要机制。Kubernetes提供了两种种类型…...
当下AI智能硬件方案浅谈
背景: 现在大模型出来以后,打破了常规的机械式的对话,人机对话变得更聪明一点。 对话用到的技术主要是实时音视频,简称为RTC。下游硬件厂商一般都不会去自己开发音视频技术,开发自己的大模型。商用方案多见为字节、百…...
STL 2迭代器
文章目录 1.迭代器2.输入迭代器3.输出迭代器1.插入迭代器 4.前向迭代器5.双向迭代器6.随机访问迭代器7.不同容器返回的迭代器类型1.输入 / 输出迭代器2.前向迭代器3.双向迭代器4.随机访问迭代器5.特殊迭代器适配器6.为什么 unordered_set 只提供前向迭代器? 1.迭代器…...