位运算基础与进阶
一、 核心操作符概览
| 操作符 | 名称 | 逻辑规则 | 常用口诀 |
& | 按位与 | 同 1 为 1，否则为 0 | 有 0 则 0 |
| | 按位或 | 有 1 为 1，全 0 为 0 | 有 1 则 1 |
^ | 按位异或 | 不同为 1，相同为 0 | 相同为 0，不同为 1 |
~ | 按位取反 | 0 变 1，1 变 0 | 全部翻转 |
<< | 左移 | 整体左移，右边补 0 | 相当于乘以 $2^{n}$ |
>> | 右移 | 整体右移，左边补符号位 | 相当于除以 $2^{n}$ |
二、 常用位运算技巧（必背）
1. 基础置位操作（针对第i位）
假设变量为n，位数从 0 开始。
获取第
i位的值：(n >> i) & 1（结果为 0 或 1）。将第
i位置 1：n |= (1 << i)。将第
i位清 0：n &= ~(1 << i)。翻转第
i位：n ^= (1 << i)。
2. 奇偶性与整除判断
判断奇偶：
n & 1结果为
1是奇数，为0是偶数（比n % 2快）。
判断是否是 2 的幂次：
n > 0 && (n & (n - 1)) == 0原理：2 的幂次二进制只有一个 1，
n-1会让该位变 0 且低位全变 1。
3. 交换两个数（不使用中间变量）
a ^= b; b ^= a; a ^= b;注意：如果
a和b指向同一个内存地址（即i == j），此方法会让变量变为 0。
4. 获取最低位的 1（Lowbit）
公式：
n & -n应用：这是树状数组（Binary Indexed Tree）的核心。
原理：负数在计算机中以补码存储（反码 + 1），相与后只保留最右边的 1。
三、 进阶：状态压缩（State Compression）
在解决动态规划（DP）或搜索问题时，常用一个int或long long来表示一组状态。
全集：
(1 << n) - 1（表示 $n$ 个位置全是 1）。遍历所有子集：
for (int i = 0; i < (1 << n); ++i) { // i 就是一种状态，通过 (i >> j) & 1 判断第 j 个元素是否存在 }
在调试时，利用<bitset>观察变化是最直观的：
#include <bitset> #include <iostream> void debug(int n) { std::cout << std::bitset<8>(n) << std::endl; // 查看低8位 }