我在Delphi中编写一个简单的BigInteger类型.此类型由无符号32位整数数组(我称之为四肢),计数(或大小)和符号位组成.数组中的值被解释为绝对值,因此这是符号幅度表示.这有几个优点,但有一个缺点.
像和和,或者xor这样的按位运算有两个补码语义.如果两个BigIntegers都有正值,则没有问题,但负BigIntegers的大小必须通过否定转换为二进制补码.这可能是一个性能问题,因为如果我们这样做,比方说
C := -A and -B;
然后我必须在执行和操作之前否定A和B的大小.由于结果也应该是否定的,我必须否定结果,以便再次获得正数.对于大型BigIntegers,否定最多三个值可能会产生相当大的性能成本.
请注意,我知道如何做到这一点并且结果是正确的,但我想避免由大数组的必要否定引起的缓慢.
例如,我知道一些快捷方式
C := not A;
可以通过计算来实现
C := -1 - A;
这就是我做的,结果很好.这不像加法或减法那样有效,因为它避免了操作之前(和之后)的否定.
题
我的问题是：是否有类似的法律我可以用来避免否定“负面”BigIntegers的数量？我的意思是像计算不使用减法？
我的意思是简单或不那么简单的法律
not A and not B = not (A or B) // = is Pascal for == not A or not B = not (A and B)
但后来为-A和/或-B等我知道
(-A and -B) <> -(A or B) // <> is Pascal for !=
不是真的,但也许有类似的东西？
我根本找不到任何与负值和按位运算相关的定律,如果它们存在的话.因此我的问题.
解决方法
上次我检查否定工作是这样的：
-A = not(A) + 1; or -A = not(A - 1); that means that -A and -B = not(A - 1) and not(B - 1)
如果我们在前面添加另一个NOT而不是我们可以替换而不是
用或
not(-A and -B) = not(not(A - 1) and not(B - 1)) = (A - 1) or (B - 1)
我们仍然需要做一个昂贵的不是最后,但因为不是如此接近 – 我们可以欺骗和替换昂贵的不便宜 – 如此：
-(-A and -B) = (A-1) or (B-1) + 1;
最后结果将是：
(-A and -B) = -((A-1) or (B-1) + 1);
这应该比翻转所有位快得多.
实施起来非常便宜,因为：
>否定是一个简单的位翻转你的符号字节.
在过度使用的情况下,> 1 / -1将很快耗尽进位/借位(仅有1/2 ^ 32个案例将进/下一个分支).
同样适用于;不是或非常接近和.