我正在研究一种我正在尝试优化的算法,它基本上有很多小技巧,然后在严格的反馈中添加了一些内容。如果我可以对加法器使用进位保存加法,它真的会帮助我加快速度,但我不确定我是否可以通过加法分配操作。
具体来说,如果我代表:
a = sa+ca (state + carry)
b = sb+cb
我可以用 s 和 c 来表示 (a >>> r) 吗?怎么样| b和a&b?
我正在研究一种我正在尝试优化的算法,它基本上有很多小技巧,然后在严格的反馈中添加了一些内容。如果我可以对加法器使用进位保存加法,它真的会帮助我加快速度,但我不确定我是否可以通过加法分配操作。
具体来说,如果我代表:
a = sa+ca (state + carry)
b = sb+cb
我可以用 s 和 c 来表示 (a >>> r) 吗?怎么样| b和a&b?
想一想...
sa = 1 ca = 1
sb = 1 cb = 1
a = sa + ca = 2
b = sb + cb = 2
(a | b) = 2
(a & b) = 2
(sa | sb) + (ca | cb) = (1 | 1) + (1 | 1) = 1 + 1 = 2 # Coincidence?
(sa & sb) + (ca & cb) = (1 & 1) + (1 & 1) = 1 + 1 = 2 # Coincidence?
让我们尝试一些其他值:
sa = 1001 ca = 1 # Binary
sb = 0100 cb = 1
a = sa + ca = 1010
b = sb + cb = 0101
(a | b) = 1111
(a & b) = 0000
(sa | sb) + (ca | cb) = (1001 | 0101) + (1 | 1) = 1101 + 1 = 1110 # Oh dear!
(sa & sb) + (ca & cb) = (1001 & 0101) + (1 & 1) = 0001 + 1 = 2 # Oh dear!
因此,通过 4 位反例证明您不能在加法上分配 AND 或 OR。
'>>>'(无符号或逻辑右移)怎么样。使用最后一个示例值,并且 r = 1:
sa = 1001
ca = 0001
sa >>> 1 = 0101
ca >>> 1 = 0000
(sa >>> 1) + (ca >>> 1) = 0101 + 0000 = 0101
(sa + ca) >>> 1 = (1001 + 0001) >>> 1 = 1010 >>> 1 = 0101 # Coincidence?
让我们看看这是否也是巧合:
sa = 1011
ca = 0001
sa >>> 1 = 0101
ca >>> 1 = 0000
(sa >>> 1) + (ca >>> 1) = 0101 + 0000 = 0101
(sa + ca) >>> 1 = (1011 + 0001) >>> 1 = 1100 >>> 1 = 0110 # Oh dear!
再次反例证明。
所以逻辑右移也不是分配在加法上的。
不,您不能在二元运算符上分配 AND 或 OR。
解释
设 P 是一个命题,其中 P:(A+B)&C = A&C + B&C
让我们取 A=2,B=3 => A+B=5。
我们要证明 A&C + B&C != (A+B)&C
A=2=010
B=3=011
让 010&C = x,其中 x 是某个整数,其值是 010 和 C 的按位与的结果
类似地 011&C = y,其中 y 是某个整数,其值是 011 和 C 的按位与的结果
因为我们不能说 P 对自然数集合({0,1,...})中的所有 C 都成立,因此 P 为假。
在这种情况下,取 C=2=010
x=010 & 010 = 010 = 2
y=011 & 010 = 010 = 2
5&2=101 & 010 = 000 = 0
显然, x+y!=0 ,这意味着 (A+B)&C != A&C + B&C。
由此证明!