6.5 位运算

位运算常见于代码中的优化，贴近计算机的物理逻辑，是计算机解决问题的优雅方案。

推荐阅读：位运算

6.5.1 常见技巧解读

语句	释义
int mid = l + r >> 1;	整数意义上>>右移 $ 1$ 位相当于除以 ，反之左移为乘
if (n & 1);	相当于 if (n % 2)，判断奇数
while (~scanf("%d", &x));	，%20%3D%200#card=math&code=%5Csim%28-1%29%20%3D%200&id=gwnSe)，读入直至文件末尾
int inf = 1 << 30;	取得一个大整数值作为无穷，但 inf * 2会整形溢出
flag ^= 1;	布尔型变量取反
bool bit = a >> b & 1;	获取 a的右起第 b位，最低位编号为 0
mask &#124;= 1 << i;	将 mask的右起第 i位设为 1
mask &= ~(1 << i);	将 mask的右起第 i位设为 0
mask ^= (1 << i);	将 mask的右起第 i位取反

注意，这些条目并非背诵科目，只是起到索引作用。如有疑问，请及时查阅相关资料，领会其精神。

6.5.2 异或

异或，简称 xor，符号为 ⊕。简单来说，异或运算的规则是「相同得零，不同得一」。

1 ⊕ 1 = 0
1 ⊕ 0 = 1
0 ⊕ 1 = 1
0 ⊕ 0 = 0

在程序中，使用 a ^ b 计算两个整数按位异或的结果，也就是把它们二进制表示的每一位进行异或运算。

按位异或运算有如下基本规律：

也因此有：

异或也被叫做不进位加法，也能够解释这种特性。

例题：力扣 136. 只出现一次的数字

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

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1: 输入: [2,2,1] 输出: 1

示例 2: 输入: [4,1,2,1,2] 输出: 4

思路：同一个数异或两次，结果为零。对所有数组元素求异或和，即为只出现一次的数字。

参考代码

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        // STL，仅力扣平台使用
        // return accumulate(nums.begin(), nums.end(), 0, bit_xor());
        int ans = 0;
        for (int i=0; i<nums.size(); ++i) {
            ans ^= nums[i];
        }
        return ans;
    }
};

6.5.3 状态压缩 / 二进制枚举

「状态压缩」原本出自「状态压缩 DP」，超过本篇讨论的范畴。但其思想可应用于解题，十分重要——用二进制连续的 0 - 1 串可以表示状态。

例题：蓝桥 算法训练 和为T

问题描述

从一个大小为n的整数集中选取一些元素，使得它们的和等于给定的值T。每个元素限选一次，不能一个都不选。

输入格式

第一行一个正整数n，表示整数集内元素的个数。
第二行n个整数，用空格隔开。
第三行一个整数T，表示要达到的和。

输出格式

输出有若干行，每行输出一组解，即所选取的数字，按照输入中的顺序排列。
　　若有多组解，优先输出不包含第n个整数的；若都包含或都不包含，优先输出不包含第n-1个整数的，依次类推。
　　最后一行输出总方案数。

样例输入 5 -7 -3 -2 5 9 0

样例输出 -3 -2 5 -7 -2 9 2

数据规模和约定
集合中任意元素的和都不超过 long 的范围

如果您已经掌握算法详解篇「深度优先搜索」的内容，可以马上想到的是 DFS 方法——面对最多 22 个不同物品选与不选的决策，共有 种不同决策（题目说明不能一个也不选）。

我们这里介绍利用二进制枚举这些不同状态的方法。这些状态用十进制数编号为 ，对应二进制数的后 位为 _2#card=math&code=%280000000000000000000001%29_2&id=gGNxE) 到 _2#card=math&code=%281111111111111111111111%29_2&id=Pa6Rb) 。这些每一个 或 就用来表示 a[] 下标从右数对应位置的数的选与不选（选择为 1，不选为 0）。比如，_2#card=math&code=%28010%29_2&id=V1Llu)就表示在数组的三个元素中，选择 a[1] ，不选 a[0] 和 a[2]。

参考代码

#include <bits/stdc++.h>
using namespace std;
int a[30];
int n, t;
int main() {
    cin >> n;
    for (int i=0; i<n; ++i) {
        cin >> a[i];
    }
    cin >> t;            // 目标
    int cnt = 0;        // 找到的方案计数
    // 二进制枚举状态 [1, 2^22-1]
    for (int i=1; i<(1<<n); ++i) {
        int sum = 0;    // 当前状态下，计算选出的数的和
        // 枚举二进制数的每一位
        for (int j=0; j<n; ++j) {
            bool bit = i >> j & 1;    // 取出当前位
            if (bit) {                // 确认选中的情况，加入求和
                sum += a[j];
            }
        }
        if (sum == t) {                // 满足目标和，开始打印
            ++cnt;
            bool head = true;        // 是否找到过第一个元素
            // 再次枚举二进制数的每一位
            for (int j=0; j<n; ++j) {
                if (i >> j & 1) {    // 确认选中的情况
                    if (!head) cout << ' ';    // 严谨输出
                    else head = false;
                    cout << a[j];
                }
            }
            cout << endl;
        }
    }
    cout << cnt << endl;
    return 0;
}

练习：蓝桥 算法训练 审美课

此题需要较好运用位运算的基本操作。

原创题解：“蓝桥杯”练习系统 ALGO-194 试题 算法训练 审美课

写题解的时候，算法经验还比较浅，各种写法也不是很优雅。不过关键之处讲的倒是很到位。事实上，这是利用二进制串，作为哈希表的键；用大数组作为哈希表。这个哈希表存储一种学生评判状态的频数。这里很巧妙的是，利用异或运算（或是题解中的满载整数（自命名）做减法）可以直接算出相反的状态的二进制数。

参考代码

#include <bits/stdc++.h>
using namespace std;
int freq[1 << 20];    // 数组哈希表
int n, m;
int main() {
    cin >> n >> m;
    // 枚举学生
    for (int i=0; i<n; ++i) {
        int mask = 0;
        // 枚举 mask 的每一位
        for (int j=0; j<m; ++j) {
            bool bit;
            cin >> bit;
            // 如果选中，就把这一位设成 1
            if (bit) {
                mask |= 1 << j;    // 0 | 1 = 1，设为 1 的写法
            }
        }
        ++freq[mask];
    }
    int ans = 0;
    // 满载整数，是一个与用到的二进制数的位数相同的，全 1 二进制数
    int N = (1 << m) - 1;
    for (int i=0; i<(1<<m); ++i) {
        ans += freq[i] * freq[N ^ i];    // 异或和减法都能实现取反
    }
    cout << ans / 2 << endl;    // 正反统计过两次，答案应除以二
    return 0;
}

代码中 mask 常常是一个状态压缩二进制串的命名。