对带符号的大整数进行位运算

Question

我正在使用Delphi编写一个简单的BigInteger类型。这种类型由无符号32位整数数组（我称之为“limbs”）、计数（或大小）和符号位组成。数组中的值被解释为绝对值，因此这是一种符号-幅度表示法。这有几个优点，但也有一个缺点。

按位操作如“and”、“or”、“xor”和“not”具有二进制补码语义。如果两个BigInteger都具有正值，则没有问题，但负的BigInteger的幅度必须通过取反转换为二进制补码。这可能会导致性能问题，例如：

C := -A and -B;

如果要执行and操作，我必须先否定A和B的大小。由于结果也应该是负数，因此我还必须否定结果以获得正的大小。对于大型BigInteger，否定多达三个值可能会带来相当大的性能成本。

请注意，我知道如何做到这一点，并且结果是正确的，但我想避免由必要的大数组否定引起的缓慢。

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

C := not A;

可以通过计算来实现

C := -1 - A;

这就是我所做的，结果很好。这使得not比加法或减法性能差，因为它避免了操作之前（和之后）的否定。

问题

我的问题是：是否有类似的规则可以用来避免否定“负”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 !=

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

我根本找不到与负值和按位操作相关的法律，如果它们存在的话。因此我的问题。

- Rudy Velthuis

---

我想向他人学习逻辑。我想学习并自己应用所学的知识。我已经有一些可行的方法，并且它们运作良好。但我始终愿意改进。正如我所说，寻找知识没有错，但简单地复制其他人（GPL许可的）的代码并不是我的目标。 - Rudy Velthuis

如果你想要一个干净的实现，那就自己动手吧。如果你让别人告诉你该怎么做，你怎么知道你还是干净的呢？假设我阅读了另一个库，找出它如何解决这些问题，然后在这里写出答案。那和你阅读代码有什么不同呢？ - David Heffernan

你可以使用二进制补码来处理 BigInteger。最高位的 limb 将是二进制补码有符号类型，而其余 limb 的类型则为无符号类型。这样实现起来会更容易，因为大多数操作对于有符号和无符号类型都是相同的。 - phuclv

从根本上讲，我认为你不从他人身上学习是愚蠢的。在我看来，拒绝接触领先的现有实现是愚蠢的行为。 - David Heffernan

写自己的代码并不傻，这真的是巩固学习的方式。但如果我是你，我会阅读所有主要 bigint 库中的代码，并阅读该代码中发现的参考文献。 - David Heffernan

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，那么我们可以用 OR 替换 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的情况会进位/借位到下一个枝干）。

对于or也是同样的道理；not or与and非常接近。

- Johan

---

谢谢，这真的帮了我很多。虽然还需要两个减法、一个加法和一个否定，所以可能并没有真正简化事情。我会检查是否可以再走一些捷径。 - Rudy Velthuis

就我实现而言，否定操作所需的时间与减法或加法的时间相差不大，据我所知，都是O(n)级别的。 - Rudy Velthuis

请注意，取反符号位并执行简单的“与”操作与执行2的补码取反和“与”操作非常不同。因此，实现真的非常便宜。 - Johan

你说得对。我会检查一下如何优化-1的方式。 - Rudy Velthuis

但请注意，我仍然需要对完整数组进行“或”操作，这是无法消除的。 <g> - Rudy Velthuis

Answer 2

我的问题是：是否有类似的法律可以避免否定“负”BigIntegers的大小？ 是的，我以前做过你想做的事情-请参见here，105-115行（或者最好下载存储库）。奇怪的是，我也使用“Limb”这个术语。例如，arrAndTwoCompl计算正数和负数的按位and，arrAndTwoCompl2计算两个负数的按位and。我从GMP来源中获得了这些“法律”。不要重新发明大整数，只需使用它们。

- kludg

---

我可以使用GMP。但是我想重新发明它们。我这样做只是为了好玩，没有任何紧迫的期限。 - Rudy Velthuis

大多数bigint库使用术语“limb”，据我所知。 - David Heffernan

Knuth 可能是第一个在他的 TAOCP 中使用这个术语的人。那是我第一次看到它的地方。 - Rudy Velthuis

DK 是否解决了这个问题？ - David Heffernan

@David：如果他有的话，我找不到。 - Rudy Velthuis