当前位置: 首页 > news >正文

[特殊字符] 蓝桥杯 Java B 组 之位运算(异或性质、二进制操作)

Day 6:位运算(异或性质、二进制操作)


📖 一、位运算简介

位运算是计算机底层优化的重要手段,利用二进制操作可以大大提高运算速度。常见的位运算包括:

  • 与(&)a & b,如果两个二进制位都为 1,结果为 1,否则为 0
  • 或(|)a | b,如果两个二进制位中至少有一个为 1,结果为 1,否则为 0
  • 异或(^)a ^ b,如果两个二进制位不同,结果为 1,否则为 0
  • 取反(~)~a,按位取反,0110
  • 左移(<<)a << n,将 a 的二进制表示向左移动 n 位,相当于 a * 2^n
  • 右移(>>)a >> n,将 a 的二进制表示向右移动 n 位,相当于 a / 2^n(保留符号位)。
  • 无符号右移(>>>):不保留符号位,即高位补 0

📖 二、只出现一次的数字(Single Number)

🔹 1. 题目描述

给定一个非空整数数组,除了某个数字只出现一次以外,其他数字均出现两次。请找出这个只出现一次的数字。

示例

输入: nums = [4, 1, 2, 1, 2]
输出: 4

🔹 2. 思路与分析

  • 利用异或运算 ^
    • 性质1a ^ a = 0,任意数与自身异或为 0
    • 性质2a ^ 0 = a,任意数与 0 异或仍是自身。
    • 性质3:异或满足交换律结合律,即 a ^ b ^ c = a ^ c ^ b,顺序无关。
    • 性质4a ^ b ^ b = a,某个数字 b 出现偶数次,它们会相互抵消。

因此,将所有数字进行异或操作,所有成对出现的数字都会抵消为 0,最终结果就是那个只出现一次的数字。


🔹 3. 代码实现(只出现一次的数字)

public class SingleNumber {public int findSingleNumber(int[] nums) {int result = 0;for (int num : nums) {result ^= num; // 利用异或运算找出唯一的数}return result;}public static void main(String[] args) {SingleNumber solution = new SingleNumber();int[] nums = {4, 1, 2, 1, 2};System.out.println("只出现一次的数字: " + solution.findSingleNumber(nums)); // 输出 4}
}

🔹 4. 代码讲解

  • result ^= num:将数组中的所有数字进行异或。
  • 成对的数字会被消除,只剩下唯一出现一次的数字。

✅ 时间复杂度:O(n),只需遍历一次数组。
✅ 空间复杂度:O(1),只使用一个变量存储结果。


📖 三、二进制中 1 的个数(Hamming Weight)

🔹 1. 题目描述

编写一个函数,计算一个整数的二进制表示中 1 的个数。

示例

输入: n = 9  (1001)
输出: 2

🔹 2. 思路与分析

方法 1️⃣:位运算逐位检查

  1. 每次检查 n 的最低位是否为 1n & 1)。
  2. 右移 n 一位(n >>= 1),直到 n 变为 0

方法 2️⃣:n & (n - 1) 高效算法

  • 性质n & (n - 1) 可以移除 n 最右边的 1,这样 1 的个数就等于操作 n & (n - 1) 多少次。

🔹 3. 代码实现(方法 1:逐位检查)

public class HammingWeight {public int countOnes(int n) {int count = 0;while (n != 0) {count += (n & 1); // 检查最低位是否为1n >>= 1; // 右移一位}return count;}public static void main(String[] args) {HammingWeight solution = new HammingWeight();int n = 9; // 二进制: 1001System.out.println("二进制中 1 的个数: " + solution.countOnes(n)); // 输出 2}
}

🔹 4. 代码实现(方法 2:n & (n - 1)

public class HammingWeightOptimized {public int countOnes(int n) {int count = 0;while (n != 0) {n &= (n - 1); // 清除最低位的1count++;}return count;}public static void main(String[] args) {HammingWeightOptimized solution = new HammingWeightOptimized();int n = 9; // 二进制: 1001System.out.println("二进制中 1 的个数: " + solution.countOnes(n)); // 输出 2}
}

🔹 5. 代码讲解

方法 1:

  • 时间复杂度 O(log n),因为 n 的二进制长度最多为 log n
  • 空间复杂度 O(1)

方法 2:

  • 时间复杂度 O(k),其中 kn1 的个数,比 O(log n) 更快。
  • 空间复杂度 O(1)

n & (n - 1) 计算次数等于 1 的个数,比 O(log n) 更快


📖 四、位运算总结

1. 常用位运算技巧

运算作用
a & 1判断 a 是否为奇数
`a(1 << k)`
a & ~(1 << k)a 的第 k 位置 0
a ^ (1 << k)翻转 a 的第 k
n & (n - 1)清除 n 的最低位 1
n & (-n)获取 n 的最低位 1

2. 位运算的常见应用

  1. 判断奇偶数n & 1 == 1(奇数),n & 1 == 0(偶数)。
  2. n 的二进制中 1 的个数
  3. 交换两个数a = a ^ b; b = a ^ b; a = a ^ b;(不使用额外空间)。
  4. 判断 n 是否是 2 的幂n > 0 && (n & (n - 1)) == 0

🎯 练习建议

  1. 理解异或运算的性质,练习 "只出现一次的数字"
  2. 熟练掌握 n & (n - 1),用于清除最低位 1 的优化技巧。
  3. 多做位运算相关题目,包括位掩码、二进制操作

相关文章:

[特殊字符] 蓝桥杯 Java B 组 之位运算(异或性质、二进制操作)

Day 6&#xff1a;位运算&#xff08;异或性质、二进制操作&#xff09; &#x1f4d6; 一、位运算简介 位运算是计算机底层优化的重要手段&#xff0c;利用二进制操作可以大大提高运算速度。常见的位运算包括&#xff1a; 与&#xff08;&&#xff09;&#xff1a;a &am…...

[MDM 2024]Spatial-Temporal Large Language Model for Traffic Prediction

论文网址&#xff1a;[2401.10134] Spatial-Temporal Large Language Model for Traffic Prediction 论文代码&#xff1a;GitHub - ChenxiLiu-HNU/ST-LLM: Official implementation of the paper "Spatial-Temporal Large Language Model for Traffic Prediction" …...

LTO优化详解

嵌入式开发过程中的LTO优化是什么意思&#xff1f;能够用来解决什么问题&#xff1f;它都优化了哪些&#xff1f;仅开启LTO真的可以优化SIZE的问题吗? 请分别回答我刚才提到的问题&#xff1f; 嗯&#xff0c;用户问关于嵌入式开发中的LTO优化&#xff0c;我需要详细解释这个概…...

分布式事务三阶段协议

分布式事务的三阶段分别是准备阶段、预提交阶段和提交 / 回滚阶段&#xff0c;以下是详细介绍&#xff1a; 三阶段提交协议可以理解为两阶段提交协议的改良版&#xff0c;是在协调者和参与者中都引入超时机制&#xff0c;并且把两阶段提交协议的第一个阶段分成了两步: 询问&am…...

LLaMA-Factory|微调大语言模型初探索(4),64G显存微调13b模型

上篇文章记录了使用lora微调deepseek-7b&#xff0c;微调成功&#xff0c;但是微调llama3-8b显存爆炸&#xff0c;这次尝试使用qlora微调HQQ方式量化&#xff0c;微调更大参数体量的大语言模型&#xff0c;记录下来微调过程&#xff0c;仅供参考。 对过程不感兴趣的兄弟们可以直…...

常用高压缩率的视频容器格式,并进行大比例压缩

常用的高压缩率视频容器格式,包括*.mp4 、*.mkv、*.webM等。     容器格式本身并不直接决定压缩率,而是取决于容器中所使用的视频编码格式等因素。不过,在常见的视频容器格式中,一些容器在搭配特定编码格式时,通常能表现出较高的压缩效率,以下是相关介绍: 1 MKV格式 …...

代码编译(词法义)

1.预处理 (Preprocessing)&#xff1a; 在这个阶段&#xff0c;编译器会处理所有以 # 开头的指令&#xff0c;如 #include、#define 等。它会把头文件的内容插入到源代码中&#xff0c;进行宏替换等预处理操作&#xff0c;生成一个纯净的代码文件。 3.词法分析 (Lexical Analy…...

android,flutter 混合开发,pigeon通信,传参

文章目录 app效果native和flutter通信的基础知识1. 编解码器 一致性和完整性&#xff0c;安全性&#xff0c;性能优化2. android代码3. dart代码 1. 创建flutter_module2.修改 Android 项目的 settings.gradle&#xff0c;添加 Flutter module3. 在 Android app 的 build.gradl…...

at32f403a rt thread led基础bsp工程测试

1.led工程官方bsp使用 导出一个独立的AT32F403A的BSP工程 下载RTT源代码 gitee更新较慢 https://gitee.com/rtthread/rt-thread github版本更新最新 https://github.com/RT-Thread/rt-thread. 切换到V5.1.0分支(使用一个发布版本可以避免不必要的bug) 导出一个独立的AT32BSP…...

DeepSeek写贪吃蛇手机小游戏

DeepSeek写贪吃蛇手机小游戏 提问 根据提的要求&#xff0c;让DeepSeek整理的需求&#xff0c;进行提问&#xff0c;内容如下&#xff1a; 请生成一个包含以下功能的可运行移动端贪吃蛇H5文件&#xff1a; 要求 蛇和食物红点要清晰&#xff0c;不超过屏幕外 下方有暂停和重新…...

【好玩的工具和命令】 ASCII 艺术生成工具: figlet

figlet 是一款用于生成 ASCII 艺术文字的工具&#xff0c;支持多种字体样式。它能将输入的文本转换为由字符组成的大型字母图案&#xff0c;广泛应用于命令行环境下的标题展示或装饰。 核心功能 生成 ASCII 文字艺术&#xff1a;将普通文本转化为大号的、由字符构成的艺术字…...

工具--安川伺服故障代码

上传一下安川伺服故障代码&#xff0c;后续结合实际维修经验&#xff0c;逐个整理分析&#xff0c;绝对超出手册经验 故障代码 故障描述 a.020/a.02 用户参数和数检查异常 1 a.021/a.02 参数格式化异常 1 a.022/a.02 系统参数和数检查异常 1 a.023/a.02 参数密码异常…...

车载软件架构 --- OEM主机厂如何打入软件供应商内部?

我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 简单,单纯,喜欢独处,独来独往,不易合同频过着接地气的生活,除了生存温饱问题之外,没有什么过多的欲望,表面看起来很高冷,内心热情,如果你身…...

AI 编程助手 cursor的系统提示词 prompt

# Role 你是一名极其优秀具有10年经验的产品经理和精通java编程语言的架构师。与你交流的用户是不懂代码的初中生&#xff0c;不善于表达产品和代码需求。你的工作对用户来说非常重要&#xff0c;完成后将获得10000美元奖励。 # Goal 你的目标是帮助用户以他容易理解的…...

Matlab写入点云数据到Rosbag

最近有需要读取一个点云并做处理后&#xff0c;重新写回rosbag。网上有很多读取的教程&#xff0c;但没有写入。自己写入时也遇到了很多麻烦&#xff0c;踩了一堆坑进行记录。 1. rosbag中一个lidar的msg有哪些信息&#xff1f; 通过如下代码&#xff0c;先读取一个rosbag的l…...

业务流程相关的权威认证和培训有哪些

业务流程的认证和培训种类繁多&#xff0c;旨在帮助专业人士掌握业务流程管理 (BPM) 的知识和技能&#xff0c;从而提升个人职业发展和组织运营效率。下面分别介绍&#xff1a; 一、 业务流程认证和培训的种类 业务流程的认证和培训可以大致分为以下几类&#xff0c;涵盖了不…...

基于Spring Boot的兴顺物流管理系统设计与实现(LW+源码+讲解)

专注于大学生项目实战开发,讲解,毕业答疑辅导&#xff0c;欢迎高校老师/同行前辈交流合作✌。 技术范围&#xff1a;SpringBoot、Vue、SSM、HLMT、小程序、Jsp、PHP、Nodejs、Python、爬虫、数据可视化、安卓app、大数据、物联网、机器学习等设计与开发。 主要内容&#xff1a;…...

【算法系列】荷兰国旗问题:三指针法原地排序

一、题目(leetcode75 颜色分类 --三分数组) 二、思路 算法核心&#xff1a;三指针分治策略 该问题被称为“荷兰国旗问题”&#xff08;Dutch National Flag Problem&#xff09;&#xff0c;由计算机科学家Edsger Dijkstra提出。其核心思想是通过三个指针将数组划分为三个区…...

DeepSeek R1本地+私有云版医疗AI部署开发成功案例技术剖析

1. 引言 1.1 研究背景与意义 随着科技的飞速发展,人工智能(AI)在医疗领域的应用正逐渐成为推动医疗行业变革的重要力量。近年来,医疗 AI 取得了显著的进展,从疾病诊断、药物研发到医疗管理等各个环节,AI 技术都展现出了巨大的潜力。它能够处理和分析海量的医疗数据,为…...

ARM64 Trust Firmware [五]

本章介绍 ATF 中的 Runtime Service 是如何定义和被调用的。 要了解 SMC&#xff0c;必须从 SMC 指令本身开始&#xff0c;其指令如下图&#xff1a; 指令格式为&#xff1a;SMC #<imm>&#xff0c;从官方文档了解到该指令只能在 EL1 以及更高的异常等级上调用&#xff…...

uniapp 对接腾讯云IM群组成员管理(增删改查)

UniApp 实战&#xff1a;腾讯云IM群组成员管理&#xff08;增删改查&#xff09; 一、前言 在社交类App开发中&#xff0c;群组成员管理是核心功能之一。本文将基于UniApp框架&#xff0c;结合腾讯云IM SDK&#xff0c;详细讲解如何实现群组成员的增删改查全流程。 权限校验…...

安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件

在选煤厂、化工厂、钢铁厂等过程生产型企业&#xff0c;其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进&#xff0c;需提前预防假检、错检、漏检&#xff0c;推动智慧生产运维系统数据的流动和现场赋能应用。同时&#xff0c;…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)

服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

【磁盘】每天掌握一个Linux命令 - iostat

目录 【磁盘】每天掌握一个Linux命令 - iostat工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景 注意事项 【磁盘】每天掌握一个Linux命令 - iostat 工具概述 iostat&#xff08;I/O Statistics&#xff09;是Linux系统下用于监视系统输入输出设备和CPU使…...

基于当前项目通过npm包形式暴露公共组件

1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹&#xff0c;并新增内容 3.创建package文件夹...

什么是库存周转?如何用进销存系统提高库存周转率?

你可能听说过这样一句话&#xff1a; “利润不是赚出来的&#xff0c;是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业&#xff0c;很多企业看着销售不错&#xff0c;账上却没钱、利润也不见了&#xff0c;一翻库存才发现&#xff1a; 一堆卖不动的旧货…...

【决胜公务员考试】求职OMG——见面课测验1

2025最新版&#xff01;&#xff01;&#xff01;6.8截至答题&#xff0c;大家注意呀&#xff01; 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:&#xff08; B &#xff09; A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...

GitHub 趋势日报 (2025年06月08日)

&#x1f4ca; 由 TrendForge 系统生成 | &#x1f310; https://trendforge.devlive.org/ &#x1f310; 本日报中的项目描述已自动翻译为中文 &#x1f4c8; 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...

2023赣州旅游投资集团

单选题 1.“不登高山&#xff0c;不知天之高也&#xff1b;不临深溪&#xff0c;不知地之厚也。”这句话说明_____。 A、人的意识具有创造性 B、人的认识是独立于实践之外的 C、实践在认识过程中具有决定作用 D、人的一切知识都是从直接经验中获得的 参考答案: C 本题解…...

【从零学习JVM|第三篇】类的生命周期(高频面试题)

前言&#xff1a; 在Java编程中&#xff0c;类的生命周期是指类从被加载到内存中开始&#xff0c;到被卸载出内存为止的整个过程。了解类的生命周期对于理解Java程序的运行机制以及性能优化非常重要。本文会深入探寻类的生命周期&#xff0c;让读者对此有深刻印象。 目录 ​…...