讨论详情 - 长治信未来奥赛OJ

位运算（异或 ^、按位与 &、按位或 |）并不是普通的加减乘除，但它们在数学结构上，与普通的算术有着非常严密的对应关系。尤其是在信息学和数学的**布尔环（GF(2)多项式环）**中，它们构成了完美的运算体系。

与普通算术运算的定律，分成了**“相似律”、“特殊分配律”和“专属定律”**三大类

这些定律在普通算术（例如 $a+b=b+a$ 或 $a \times b = b \times a$ ）中也存在，在按位运算中完全适用。

定律名称	运算	公式表达	普通算术类比
交换律	异或、与、或	$A \oplus B = B \oplus A$ $A \& B = B \& A$ $A \mid B = B \mid A$	加法、乘法
结合律		$(A \oplus B) \oplus C = A \oplus (B \oplus C)$ $(A \& B) \& C = A \& (B \& C)$ $(A \mid B) \mid C = A \mid (B \mid C)$	加法、乘法
恒等律		$A \oplus 0 = A$ $A \& 1 = A$ $A \mid 0 = A$	普通加法： $A+0=A$ 普通乘法： $A\times1=A$

在这里，我们要把异或 ^ 类比为普通数学的 “加法”，把按位与 & 类比为 “乘法”。

按位与对异或的分配律（✅ 成立）
- 公式： $A \& (B \oplus C) = (A \& B) \oplus (A \& C)$
- 普通算术类比：这就像普通数学里的乘法分配律： $A \times (B + C) = A \times B + A \times C$ 。
- （注意：计算机底层的加法器原理就是利用这个关系实现的， $A+B = (A \oplus B) + ((A \& B) << 1)$ ）。
按位与与按位或的互相分配律（✅ 成立）
- 公式1： $A \& (B \mid C) = (A \& B) \mid (A \& C)$
- 公式2： $A \mid (B \& C) = (A \mid B) \& (A \mid C)$
- 普通算术类比：普通数学的乘法对加法有分配律，但加法对乘法没有分配律。但在位运算的布尔代数中，与和或是完全对称的，它们互相都有分配律！
- 举例验证：假设 $A=1, B=1, C=0$ 。左边： $1 \& (1 \mid 0) = 1 \& 1 = 1$ 。右边： $(1 \& 1) \mid (1 \& 0) = 1 \mid 0 = 1$ 。

🚨 特别警告：按位或对异或是不存在分配律的！

位运算是基于二进制的，所以它拥有一些普通整数运算完全没有的性质：

定律名称	运算	公式表达	核心含义
幂等律	按位与、按位或	$A \& A = A$ $A \mid A = A$	普通算术中 $A \times A = A^2$ ，而位运算自己和自己操作不会变大。
互补律	按位与、按位或	$A \& (\sim A) = 0$ $A \mid (\sim A) = \text{全1}$	每一位要么是0，要么是1，两者互斥。
自反律	异或	$A \oplus A = 0$	重点记住：异或一个数两次，等于原数。
消去律	异或	$A \oplus B \oplus B = A$	极其重要：把 $X \oplus Y \oplus Y$ 看成 $X + Y - Y$ 。

在编程和算法中，你能用上加减法的地方，绝大部分都可以用异或替换，但要注意“进位”问题。

加减替代： $A \oplus B$ 等于 $A$ 加 $B$ 但不进位。而 $A \oplus B \oplus B = A$ 完美模拟了 $A + B - B = A$ 。
应用在算法中：如果你解方程组时发现不用考虑系数的大小，只关心“奇偶性”或“0/1”状态，你可以直接把矩阵的加法和减法替换成 ^，把行乘以系数替换成 &。这就是你在上一张图里“开关问题”能够使用异或高斯消元的最根本数学原理。

目前还没有评论...

位运算的一些定律