【算法日记 #01】[特殊字符]【算法进阶】位运算精华总结：XOR 与 OR 的实战模型[特殊字符]

本文目录 前言一、 什么是异或XOR1. 真值表2. 核心性质背下来面试很有用二、 经典例题实战例题 1不使用临时变量交换两个数解析利用了异或的自反性。虽然在现代开发中这种写法的可读性不如 swap但它是理解位运算的绝佳例子。例题 2找单身狗只出现一次的数字三、 什么是按位或OR1. 真值表2. 核心性质贪心算法常考点四、 进阶挑战按位或OR的贪心实战例题 3积木价值最大化按位或的贪心策略五、 总结与反思 前言在算法竞赛如蓝桥杯和日常的面试刷题中我们经常会遇到一些看似需要双重循环暴力破解实则可以通过**位运算Bitwise Operations**瞬间秒杀的题目。位运算直接操作底层的 0 和 1不仅执行速度极快不产生进位还能把几十行的代码浓缩成短短几行。今天这篇算法日记我将结合最近在集训中遇到的两道经典例题带大家彻底搞懂异或^和按位或|的核心特性与贪心实战模型食用说明本文所有实战代码均采用 C 实现包含极其详细的思路推导。如果您觉得有帮助欢迎点赞收藏本项目源码已同步至我的 GitHub 仓库。一、 什么是异或XOR异或是一种二进制位运算它的逻辑非常简单相同为 0不同为 1。1. 真值表ABA ^ B0000111011102. 核心性质背下来面试很有用归零律a ⊕ a 0 a \oplus a 0a⊕a0自己异或自己等于 0恒等律a ⊕ 0 a a \oplus 0 aa⊕0a任何数异或 0 依然等于自身交换律/结合律a ⊕ b b ⊕ a a \oplus b b \oplus aa⊕bb⊕a二、 经典例题实战例题 1不使用临时变量交换两个数题目描述给定两个整数a和b在不使用第三个变量的情况下交换它们的值。代码实现#includeiostreamusingnamespacestd;intmain(){inta10,b20;aa^b;ba^b;// 此时 b (a^b) ^ b aaa^b;// 此时 a (a^b) ^ a bcout交换后a a, b bendl;return0;}解析利用了异或的自反性。虽然在现代开发中这种写法的可读性不如 swap但它是理解位运算的绝佳例子。例题 2找单身狗只出现一次的数字题目描述给定一个非空整数数组除了某个元素只出现一次以外其余每个元素均出现两次。找出那个只出现了一次的元素。思路根据异或的性质两个相同的数异或结果为 0归零律a ⊕ a 0 a \oplus a 0a⊕a0而任何数与 0 异或都等于它本身恒等律a ⊕ 0 a a \oplus 0 aa⊕0a。如果我们把数组里所有的数字全部“连环异或”一遍那些成对出现的数字都会互相抵消变成 0最后剩下的结果就是那个“单身”的数字。代码实现#includeiostream#includevectorusingnamespacestd;intfindSingleNumber(vectorintnums){intres0;// 遍历数组中的每一个数字进行连环异或for(intx:nums){res^x;}returnres;}intmain(){vectorintv{4,1,2,1,2};cout只出现一次的数字是: findSingleNumber(v)endl;// 预期输出 4return0;}三、 什么是按位或OR按位或符号为|同样是一种非常基础的二进制位运算。它的逻辑非常霸道只要参与运算的两个位中有一个为 1结果就为 1只有两边都为 0 时结果才为 0。形象一点说这是一个**“填坑”**操作1 代表有土0 代表是坑。只要两边有一边有土这个坑就能被填平变成 1。1. 真值表ABA | B0000111011112. 核心性质贪心算法常考点恒等律a ∣ 0 a a \mid 0 aa∣0a和 0 进行或运算保持原值不变自反律a ∣ a a a \mid a aa∣aa和自己进行或运算还是自己 递增性极其重要a ∣ b ≥ max ⁡ ( a , b ) a \mid b \ge \max(a, b)a∣b≥max(a,b)。按位或的结果永远大于或等于参与运算的任何一个数这就是为什么在算法题中要求“最大价值/最大结果”时经常会用到按位或。四、 进阶挑战按位或OR的贪心实战例题 3积木价值最大化按位或的贪心策略题目描述从1 , 2 , … , n 1, 2, \dots, n1,2,…,n中选出恰好k kk个不同的积木使得它们的按位或结果a 1 ∣ a 2 ∣ ⋯ ∣ a k a_1 \mid a_2 \mid \dots \mid a_ka1​∣a2​∣⋯∣ak​最大。数据范围1 ≤ k ≤ n ≤ 10 9 1 \le k \le n \le 10^91≤k≤n≤109思路解析按位或运算|的特点是只要参与运算的数字中某一位有一个 1结果的那一位就是 1。为了让最后的价值最大我们的目标是让结果的二进制位数尽可能多且每一位都尽可能为 1。情况 A当k 1 k 1k1时只能选一个数毫无疑问最大的数就是n nn本身。情况 B当k ≥ 2 k \ge 2k≥2时贪心思想登场假设n nn的最高位在第m mm位即2 m − 1 ≤ n 2 m 2^{m-1} \le n 2^m2m−1≤n2m。我们已经拥有了最大的数n nn。只要再选一个数比如2 m − 1 − 1 2^{m-1}-12m−1−1它的二进制全都是 1刚好能把n nn中所有是 0 的低位全部“填满”成 1。既然k ≥ 2 k \ge 2k≥2我们总能找到凑出全 1 的组合。结论最终的最大价值就是m mm个 1 组成的二进制数即2 m − 1 2^m - 12m−1。 避坑指南题目给定的n nn高达10 9 10^9109在寻找2 m 2^m2m时普通的int可能会在位移时溢出所以务必使用long long数据类型代码实现#includeiostreamusingnamespacestd;voidsolve(){longlongn,k;cinnk;if(k1){// 只能选一个最大就是 ncoutnendl;}else{// 寻找大于 n 的最小的 2 的整数次幂longlongres1;while(resn){res1;}// res - 1 就是我们要找的“全 1”的最大值coutres-1endl;}}intmain(){// 提升 cin/cout 速度的玄学小技巧ios::sync_with_stdio(false);cin.tie(nullptr);intT;cinT;while(T--){solve();}return0;}五、 总结与反思位运算看似只是底层枯燥的 0 和 1 的游戏但在算法的世界里它们往往能发挥出“四两拨千斤”的奇效异或^是“消除大师”利用它的归零律我们可以轻松解决成对出现的抵消问题如找单身狗或者在不引入额外空间O ( 1 ) O(1)O(1)空间复杂度的情况下巧妙交换变量。按位或|是“填坑专家”利用它的递增性在求最大值、贪心凑全 1 位数的场景中它是我们的不二之选。在日常的刷题中特别是面对10 9 10^9109这样庞大的数据范围时如果常规的O ( N ) O(N)O(N)或O ( N 2 ) O(N^2)O(N2)算法会超时不妨停下来想一想这道题能不能用位运算来进行“降维打击”写在最后算法之路虽然漫长但每搞懂一个核心模型就像在游戏里点亮了一个新技能。这是我的【算法日记】系列的第一篇希望对自己和大家都有所帮助 本文所有的实战代码均已分类上传至我的 GitHub 仓库欢迎去踩踩[https://github.com/bvanhoa72-beep/cpp-algorithms-2000]如果这篇文章对你有所启发欢迎点赞 ➕ 收藏 ➕ 关注你们的支持是我持续更新的最大动力如果有疑问也欢迎在评论区留言我们一起交流探讨~