有按位算子定律吗? [英] Are there any Bitwise Operator Laws?
问题描述
从代数定律的角度考虑,我想知道在位操作领域中是否存在与代数类似的任何官方指南.
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), IdempotentOR (|)
: Commutative, Associative, Identity (0x00), Annihilator (0xFF), IdempotentXOR (^)
: 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
intomax
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. Forx + (x << 1) = x * 3
, the inverse isx * 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.
这篇关于有按位算子定律吗?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!