---

🌟 前言

在算法竞赛（如蓝桥杯）和日常的面试刷题中，我们经常会遇到一些看似需要双重循环暴力破解，实则可以通过**位运算（Bitwise Operations）**瞬间秒杀的题目。

位运算直接操作底层的 0 和 1，不仅执行速度极快（不产生进位），还能把几十行的代码浓缩成短短几行。今天这篇算法日记，我将结合最近在集训中遇到的两道经典例题，带大家彻底搞懂 异或（^） 和 按位或（|） 的核心特性与贪心实战模型！

💡 食用说明：本文所有实战代码均采用 C++ 实现，包含极其详细的思路推导。如果您觉得有帮助，欢迎点赞收藏！本项目源码已同步至我的 GitHub 仓库。

---

一、 什么是异或（XOR）？

异或是一种二进制位运算，它的逻辑非常简单：相同为 0，不同为 1。

1. 真值表

A	B	A ^ B
0	0	0
0	1	1
1	0	1
1	1	0

2. 核心性质（背下来，面试很有用！）

• 归零律：$a\oplus a=0$（自己异或自己等于 0）
• 恒等律：$a\oplus 0=a$（任何数异或 0 依然等于自身）
• 交换律/结合律：$a\oplus b=b\oplus a$

---

二、 经典例题实战

例题 1：不使用临时变量交换两个数

题目描述：给定两个整数 a 和 b，在不使用第三个变量的情况下交换它们的值。

代码实现：

#include <iostream>
using namespace std;

int main() {
    int a = 10, b = 20;
    
    a = a ^ b;
    b = a ^ b; // 此时 b = (a^b) ^ b = a
    a = a ^ b; // 此时 a = (a^b) ^ a = b
    
    cout << "交换后：a = " << a << ", b = " << b << endl;
    return 0;
}

解析：利用了异或的自反性。虽然在现代开发中这种写法的可读性不如 swap，但它是理解位运算的绝佳例子。

例题 2：找单身狗（只出现一次的数字）

题目描述：给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

思路：
根据异或的性质，两个相同的数异或结果为 0（归零律 $a\oplus a=0$），而任何数与 0 异或都等于它本身（恒等律 $a\oplus 0=a$）。如果我们把数组里所有的数字全部“连环异或”一遍，那些成对出现的数字都会互相抵消变成 0，最后剩下的结果就是那个“单身”的数字。

代码实现：

#include <iostream>
#include <vector>
using namespace std;

int findSingleNumber(vector<int>& nums) {
    int res = 0;
    // 遍历数组中的每一个数字，进行连环异或
    for (int x : nums) {
        res ^= x; 
    }
    return res;
}

int main() {
    vector<int> v = {4, 1, 2, 1, 2};
    cout << "只出现一次的数字是: " << findSingleNumber(v) << endl; // 预期输出 4
    return 0;
}

---

三、 什么是按位或（OR）？

按位或（符号为 |）同样是一种非常基础的二进制位运算。它的逻辑非常霸道：只要参与运算的两个位中有一个为 1，结果就为 1；只有两边都为 0 时，结果才为 0。

形象一点说，这是一个**“填坑”**操作：1 代表有土，0 代表是坑。只要两边有一边有土，这个坑就能被填平（变成 1）。

1. 真值表

A	B	A | B
0	0	0
0	1	1
1	0	1
1	1	1

2. 核心性质（贪心算法常考点！）

• 恒等律：$a\mid 0=a$ （和 0 进行或运算，保持原值不变）
• 自反律：$a\mid a=a$ （和自己进行或运算，还是自己）
• 🔥 递增性（极其重要）：$a\mid b\ge \max (a,b)$。按位或的结果，永远大于或等于参与运算的任何一个数！ 这就是为什么在算法题中，要求“最大价值/最大结果”时，经常会用到按位或。

---

四、 进阶挑战：按位或（OR）的贪心实战

例题 3：积木价值最大化（按位或的贪心策略）

题目描述：
从 $1,2,\dots ,n$ 中选出恰好 $k$ 个不同的积木，使得它们的按位或结果 $a_1\mid a_2\mid \cdots \mid a_k$ 最大。（数据范围：$1\le k\le n\le 10^9$）

思路解析：
按位或运算（|）的特点是：只要参与运算的数字中某一位有一个 1，结果的那一位就是 1。
为了让最后的价值最大，我们的目标是让结果的二进制位数尽可能多，且每一位都尽可能为 1。

• 情况 A：当 $k=1$ 时
  只能选一个数，毫无疑问，最大的数就是 $n$ 本身。
• 情况 B：当 $k\ge 2$ 时（贪心思想登场）
  假设 $n$ 的最高位在第 $m$ 位（即 $2^{m-1}\le n<2^m$）。
  我们已经拥有了最大的数 $n$。只要再选一个数（比如 $2^{m-1}-1$），它的二进制全都是 1，刚好能把 $n$ 中所有是 0 的低位全部“填满”成 1。
  既然 $k\ge 2$，我们总能找到凑出全 1 的组合。
  结论：最终的最大价值就是 $m$ 个 1 组成的二进制数，即 $2^m-1$。

💡 避坑指南：
题目给定的 $n$ 高达 $10^9$，在寻找 $2^m$ 时，普通的 int 可能会在位移时溢出，所以务必使用 long long 数据类型！

代码实现：

#include <iostream>
using namespace std;

void solve() {
    long long n, k;
    cin >> n >> k;

    if (k == 1) {
        // 只能选一个，最大就是 n
        cout << n << endl;
    } else {
        // 寻找大于 n 的最小的 2 的整数次幂
        long long res = 1;
        while (res <= n) {
            res <<= 1; 
        }
        // res - 1 就是我们要找的“全 1”的最大值
        cout << res - 1 << endl;
    }
}

int main() {
    // 提升 cin/cout 速度的玄学小技巧
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

---

五、 总结与反思

位运算看似只是底层枯燥的 0 和 1 的游戏，但在算法的世界里，它们往往能发挥出“四两拨千斤”的奇效：

• 异或（^）是“消除大师”：利用它的归零律，我们可以轻松解决成对出现的抵消问题（如找单身狗），或者在不引入额外空间（$O(1)$ 空间复杂度）的情况下巧妙交换变量。
• 按位或（|）是“填坑专家”：利用它的递增性，在求最大值、贪心凑全 1 位数的场景中，它是我们的不二之选。

在日常的刷题中（特别是面对 $10^9$ 这样庞大的数据范围时），如果常规的 $O(N)$ 或 $O(N^2)$ 算法会超时，不妨停下来想一想：这道题能不能用位运算来进行“降维打击”？

---

🚀 写在最后：
算法之路虽然漫长，但每搞懂一个核心模型，就像在游戏里点亮了一个新技能。这是我的【算法日记】系列的第一篇，希望对自己和大家都有所帮助！

💻 本文所有的实战代码均已分类上传至我的 GitHub 仓库，欢迎去踩踩：
[https://github.com/bvanhoa72-beep/cpp-algorithms-2000]

如果这篇文章对你有所启发，欢迎 点赞 ➕ 收藏 ➕ 关注！你们的支持是我持续更新的最大动力！如果有疑问，也欢迎在评论区留言，我们一起交流探讨~