computer-science - 是否有任何按位运算符法则？

Question

从代数定律的角度思考，我想知道在位操作领域是否存在任何官方指南，类似于代数。

代数例子

a - b =/= b - a

让a = 7和b = 5

• a - b = 2
• b - a = -2

让a = 10和b = 3

• a - b = 7
• b - a = -7

因此if a > b，b - a将负等价于a - b。正因为如此，我们可以说

|a - b| = |b - a|。

其中|x|表示 的绝对值x。

按位示例

a | b =/= a + b

      00001010 = 10
  OR  00000101 = 5 
  -----------------
      00001111 = 15

注意无符号字节操作：10 | 5 = 15，它是同义词10 + 5 = 15

但是，如果两者a和b等于 5 并且我们OR它们，结果将是 5，因为a = b，这意味着我们只是在相互比较相同的确切位，因此没有任何新内容。

同样，如果b = 7和a = 10我们OR他们，我们将有 15 个。这是因为

    00001010 = 10
 OR 00000111 = 7
 -----------------
    00001111 = 15

因此，我们可以有效地得出结论a | b =/= a + b。

Answer 1

仅在操作数的相应位之间应用的布尔运算符的位运算遵循类似于布尔代数定律的定律，例如：

• AND (&): 可交换的、关联的、标识 (0xFF)、歼灭者 (0x00)、幂等
• OR (|): 可交换的、关联的、标识 (0x00)、歼灭者 (0xFF)、幂等
• XOR (^): 可交换的、关联的、标识 (0x00)、逆（本身）
• NOT (~): 逆（本身）

AND 和 OR 相互吸收：

• a & (a | b) = a
• a | (a & b) = a

有一些分配运算符对，例如：

• 与或：a & (b | c) = (a & b) | (a & c)
• 与异或：a & (b ^ c) = (a & b) ^ (a & c)
• 或超过 AND：a | (b & c) = (a | b) & (a | c)

但是请注意，XOR 不会分布在 AND 或 OR 上，OR 也不会分布在 XOR 上。

德摩根定律适用于各种形式：

• ~(a & b) = ~a | ~b
• ~(a | b) = ~a & ~b

通过推理域ℤ/2ℤ可以找到一些与 XOR 和 AND 相关的定律，其中加法对应于 XOR，乘法对应于 AND：

• AND 通过 XOR 分配
• 计算总和的乘积：(a ^ b) & (c ^ d) = (a & c) ^ (a & d) ^ (b & c) ^ (b & d)

有一些结合算术和位运算的定律：

• 通过添加减去：a - b = ~(~a + b)
• 分别添加进位：a + b = (a ^ b) + ((a & b) << 1)
• 变成min，max反之亦然：min(a, b) = ~max(~a, ~b),max(a, b) = ~min(~a, ~b)

由于被推到边缘的位的“破坏”，移位没有逆向

left shift (<<): 关联的、分配的、身份的 (0x00)

right shift (>>): 关联的、分配的、身份的 (0x00)

rotate left (rl)：关联，分配，身份（0x00），逆（rr）

rotate right (rr)：关联，分配，身份（0x00），逆（rl）

虽然移位没有逆，但由于其他定律，一些涉及移位的表达式确实具有逆，例如：

• x + (x << k)有一个逆，因为它实际上是一个奇数的乘法，而奇数有一个模乘逆模，以 2 的幂为模。对于x + (x << 1) = x * 3，倒数是x * 0xAAAAAAAB（对于 32 位，调整其他大小的常数）
• x ^ (x << k)出于类似的原因有一个逆，但通过与无进位乘法的对应关系。
• 同样x ^ (x >> k)（无符号右移）有一个逆，它只是上面的“镜像”。