当前位置: 首页 > 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…...

接口测试中缓存处理策略

在接口测试中&#xff0c;缓存处理策略是一个关键环节&#xff0c;直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性&#xff0c;避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明&#xff1a; 一、缓存处理的核…...

树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频

使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...

3.3.1_1 检错编码(奇偶校验码)

从这节课开始&#xff0c;我们会探讨数据链路层的差错控制功能&#xff0c;差错控制功能的主要目标是要发现并且解决一个帧内部的位错误&#xff0c;我们需要使用特殊的编码技术去发现帧内部的位错误&#xff0c;当我们发现位错误之后&#xff0c;通常来说有两种解决方案。第一…...

前端导出带有合并单元格的列表

// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...

大语言模型如何处理长文本?常用文本分割技术详解

为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...

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

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

Java多线程实现之Callable接口深度解析

Java多线程实现之Callable接口深度解析 一、Callable接口概述1.1 接口定义1.2 与Runnable接口的对比1.3 Future接口与FutureTask类 二、Callable接口的基本使用方法2.1 传统方式实现Callable接口2.2 使用Lambda表达式简化Callable实现2.3 使用FutureTask类执行Callable任务 三、…...

Java-41 深入浅出 Spring - 声明式事务的支持 事务配置 XML模式 XML+注解模式

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

音视频——I2S 协议详解

I2S 协议详解 I2S (Inter-IC Sound) 协议是一种串行总线协议&#xff0c;专门用于在数字音频设备之间传输数字音频数据。它由飞利浦&#xff08;Philips&#xff09;公司开发&#xff0c;以其简单、高效和广泛的兼容性而闻名。 1. 信号线 I2S 协议通常使用三根或四根信号线&a…...

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

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