异或
常用运算符：
- C/C++:
^/xor - Python:
^
真值表
| 结果 | ||
|---|---|---|
| 0 | 0 | 0 |
| 1 | 1 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
性质1：0是异或的单位元
即，0 ^ a = a，满足交换律
性质2：任何数异或自己等于0
即，a ^ a = 0
性质3：异或同一个数两次等于啥也没做
即，a ^ b ^ b = a. 因为满足结合律，且根据性质2，b ^ b = 0，再根据性质1，a ^ 0 = a.
与
真值表
| 结果 | ||
|---|---|---|
| 0 | 0 | 0 |
| 1 | 1 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
基本性质
- 交换律：
a & b = b & a - 结合律：
(a & b) & c = a & (b & c) - 分配律（对或）：
a & (b | c) = (a & b) | (a & c) - 吸收律：
a & (a | b) = a - 幂等性：
a & a = a - 单位元是二进制全为 1 的元素：
a & ~0 = a（~0就是二进制全为 1 的元素） - 零元为 0，即任意数和 0 按位与，都得 0：
a & 0 = 0 - 恒等式：
a & ~a = 0
性质一：单调性
重要单调性：a & b 的结果中，为 1 的位一定是 a 和 b 中同时为 1 的位。因此：
(a & b) <= a // 数值上不一定，但"1 的位数"一定不超过 a 和 b
(a & b) <= min(a, b) // 对无符号数成立
a & b ⊆ a // 位集合意义下，结果位是 a、b 位的交集注：仅考虑无符号数。
性质二：德摩根定律（按位版）
~(a & b) == ~a | ~b
~(a | b) == ~a & ~b应用一：作为掩码
按位与的核心用途是筛选/保留某些位：
a & 0x0F // 只保留低 4 位，其余清零
a & (1 << k) // 只保留第 k 位（结果为 0 或 2^k）
a & ~(1 << k) // 清除第 k 位，其余不变
a & mask // 结果 <= min(a, mask) 的位模式，只能"减少" 1 的位判断奇偶：
a & 1 // == 0 表示偶数，== 1 表示奇数（只看最低位）判断是否为 2 的幂：
// 原理：n 与 n-1 按位与，会把最低的 1 位及其以下全部清零。
(n & (n - 1)) == 0 // 等价于 n 是 2 的幂，n > 0 成立应用二：组合应用
a & b == (a + b - (a ^ b)) / 2 // 一个常用恒等式
a + b == (a & b) + (a | b) // 也是经典恒等式：两数相加
a ^ b == (a | b) - (a & b)常见坑
a & b == c // 被解析成 a & (b == c) ❌
(a & b) == c // ✅ 永远加括号附录
C++位运算符别名
| 替代记号 | 等价运算符 | 1 和 2 的结果 |
|---|---|---|
and | && 逻辑与 | 1 (true) |
or | | 逻辑或 | 1 (true) |
not | ! 逻辑非 | — |
** xor ** | ^ 按位异或 | 3 |
bitand | & 按位与 | 0 |
bitor | | 按位或 | 3 |
compl | ~ 按位取反 | — |
see also: 神奇的位运算