从代数定律的角度考虑,我想知道在位操作领域中是否存在与代数类似的任何官方指南.
Thinking in terms of Algebraic laws, I was wondering if there are any official guide lines which exist in the realm of bit manipulations, similar to Algebra.
代数示例
a-b =/= b-a
让 a = 7 和 b = 5
- a-b = 2
- b-a = -2
让 a = 10 和 b = 3
- a-b = 7
- b-a = -7
因此如果>b , b-a 等于 a-b 的负值.因此,我们可以说 | a-b |= | b-a | .
Thus if a > b, b - a will be the negative equivalent to a - b. Because of this, we can say |a - b| = |b - a|.
其中 | x | 表示 x 的绝对值.
按位示例
a |b =/= a + b
00001010 = 10 OR 00000101 = 5 ----------------- 00001111 = 15请注意无符号字节操作: 10 |5 = 15 ,与 10 + 5 = 15
Note the unsigned byte manipulation: 10 | 5 = 15, which is synonymous with 10 + 5 = 15
但是,如果 a 和 b 都等于5并且我们对它们进行 OR ,则结果将为5,因为 a =b ,这意味着我们只是将相同的确切位彼此进行比较,因此不会产生新的结果.
However, if both a and b equal 5 and we OR them, the result would be 5, because a = b, which means we're just comparing the same exact bits with each other, thus resulting in nothing new.
同样,如果 b = 7 , a = 10 并且我们对它们进行 OR ,我们将有15.这是因为
Likewise, if b = 7, a = 10 and we OR them we'll have 15. This is because
00001010 = 10 OR 00000111 = 7 ----------------- 00001111 = 15因此,我们可以有效地得出以下结论:b =/= a + b .
So, we can effectively conclude that a | b =/= a + b.
推荐答案按位运算只是在操作数的相应位之间应用的布尔运算符,其遵循类似于布尔代数定律的定律,例如:
Bitwise operations that are just a boolean operator applied between corresponding bits of the operands follow laws analogous to the laws of Boolean algebra, for example:
- AND(&):可交换,关联,身份(0xFF),An灭(0x00),等幂
- OR(|):可交换,关联,身份(0x00)、,灭(0xFF),等幂
- XOR(^):可交换,关联,身份(0x00),反(自身)
- NOT(〜):反(本身)
- AND (&) : Commutative, Associative, Identity (0xFF), Annihilator (0x00), Idempotent
- OR (|) : Commutative, Associative, Identity (0x00), Annihilator (0xFF), Idempotent
- XOR (^) : Commutative, Associative, Identity (0x00), Inverse (itself)
- NOT (~) : Inverse (itself)
AND和OR相互吸收:
AND and OR absorb each other:
- a&(a | b)= a
- a |(a& b)= a
有一些分布式运算符,例如:
There are some pairs of distributive operators, such as:
- AND或: a&(b | c)=(a& b)|(a& c)
- 并通过XOR: a&(b ^ c)=(a& b)^(a& c)
- 或与AND: a |(b& c)=(a | b)&(a | c)
但是请注意,XOR不会通过AND或OR进行分配,OR也不会通过XOR进行分配.
Note however that XOR does not distribute over AND or OR, and neither does OR distribute over XOR.
DeMorgans法以各种形式适用:
DeMorgans law applies in its various forms:
- 〜(a& b)=〜a |〜b
- 〜(a | b)=〜a&〜b
可以通过对字段ℤ/2ℤ进行推理来找到一些与XOR和AND相关的定律,其中加法对应于XOR且与AND相乘:
Some laws that relate XOR and AND can be found by reasoning about the field ℤ/2ℤ, in which addition corresponds to XOR and multiplication to AND:
- AND通过XOR分发
- 计算和的乘积:(a ^ b)&(c ^ d)=(a& c)^(a& d)^(b& c)^(b& d)
有些定律将算术和按位运算相结合:
There are some laws that combine arithmetic and bitwise operations:
- 添加以下内容减去: 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)
- Subtract by adding: a - b = ~(~a + b)
- Add carries separately: a + b = (a ^ b) + ((a & b) << 1)
- Turn min into max and vice versa: min(a, b) = ~max(~a, ~b), max(a, b) = ~min(~a, ~b)
由于位被破坏",移位没有反作用力
Shifts have no inverse because of the "destruction" of bits pushed to the edge
左移(<<):关联,分配,标识(0x00)
left shift (<<) : Associative, Distributive, Identity (0x00)
右移(>>):关联,分配,标识(0x00)
right shift (>>) : Associative, Distributive, Identity (0x00)
向左旋转(rl):关联,分配,标识(0x00),逆向( rr )
rotate left (rl) : Associative, Distributive, Identity (0x00), Inverse (rr)
向右旋转(rr):关联,分配,标识(0x00),逆向( rl )
rotate right (rr) : Associative, Distributive, Identity (0x00), Inverse (rl)
虽然平移没有反函数,但某些包含平移的表达式却由于其他定律而具有反函数,例如:
While shifts have no inverse, some expressions involving shifts do have inverses as consequence of other laws, for example:
- x +(x<< k)具有反函数,因为它实际上是乘以奇数的乘积,并且奇数具有模幂为2的模乘逆.对于 x +(x<< 1)= x * 3 ,反函数为 x * 0xAAAAAAAB (对于32位,请调整其他大小的常数)
- x ^(x<< k)出于相似的原因而具有逆,但是通过与无进位乘法的对应来实现.
- 类似地, x ^(x>> k)(无符号右移)具有反函数,它只是上面的镜像".
- x + (x << k) has an inverse, because it is effectively a multiplication by an odd number and odd numbers have an modular multiplicative inverse modulo a power of two. For x + (x << 1) = x * 3, the inverse is x * 0xAAAAAAAB (for 32 bits, adjust the constant for other sizes)
- x ^ (x << k) has an inverse for a similar reason, but through the correspondence with carryless multiplication.
- Similarly x ^ (x >> k) (with unsigned right shift) has an inverse, it's just the "mirror image" of the above.
更多推荐
有按位算子定律吗?
发布评论