delphi - 符号数值大整数的按位运算

Question

我正在 Delphi 中编写一个简单的 BigInteger 类型。这种类型由无符号 32 位整数数组(我称之为肢体)、计数(或大小)和符号位组成。数组中的值被解释为绝对值，因此这是符号大小表示。这有几个优点，但也有一个缺点。

像and、or、xor和not这样的按位运算具有二进制补码语义。如果两个 BigInteger 都具有正值，那么这没有问题，但负 BigInteger 的大小必须通过求反转换为二进制补码。这可能是一个性能问题，因为如果我们这样做，就会说

C := -A and -B;

那么我必须先对 A 和 B 的大小取反，然后才能执行 and 运算。由于结果也应该是负数，因此我也必须否定结果才能再次获得正值。对于大型 BigInteger，对最多三个值取反可能会产生相当大的性能成本。

请注意，我知道如何执行此操作并且结果是正确的，但我想避免因大型数组的必要否定而导致的缓慢。

例如，我知道一些快捷方式

C := not A;

可以通过计算来实现

C := -1 - A;

我就是这样做的，结果很好。这使得不如像加法或减法那样高效，因为它避免了运算之前(和之后)的求反。

问题

我的问题是:是否可以使用类似的法则来避免否定“负”BigInteger 的大小？我的意思是使用减法来计算not？

我的意思是简单或不那么简单的法律，例如

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 !=

不是真的，但也许有类似的东西？

我根本找不到任何与负值和按位运算相关的定律(如果它们存在的话)。这就是我的问题。

Answer 1

上次我检查否定是这样工作的:

-A = not(A) + 1; or
-A = not(A - 1);
that means that
-A and -B = not(A - 1) and not(B - 1)

如果我们在前面添加另一个 NOT，那么我们可以替换 and not 带有或

not(-A and -B) = not(not(A - 1) and not(B - 1)) =
(A - 1) or (B - 1)   

最后我们仍然需要做一个昂贵的not，但是因为not非常接近-，我们可以作弊并替换昂贵的not 与廉价的 - 类似:

-(-A and -B) = (A-1) or (B-1) + 1;

最终结果将是:

(-A and -B) = -((A-1) or (B-1) + 1);   

这应该比翻转所有位要快得多。

实现起来成本非常低，因为:

1. 求反是对符号字节进行简单的位翻转。
2. +1/-1 在大量情况下很快就会用完进位/借位位(只有 1/2^32 情况会进位/借位到下一个肢体)。

或也是如此； not or 与 and 非常接近。