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

因此，如果 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

位运算只是应用于操作数的相应位之间的 bool 运算符，遵循类似于 bool 代数定律的定律，例如:

• 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)
• “或”与“或”: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) (带有无符号右移)有一个逆，它只是上面的“镜像”。