符号运算符号幅度大整数

Question

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

像位运算and,or,xor并not有补语义.如果两个BigIntegers都具有正值,则这是没有问题的,但是负BigIntegers 的大小必须通过否定转换为二的补码.这可能是一个性能问题,因为如果我们这样做,比方说

C := -A and -B;

然后我必须否定的大小A和B在之前and就可以执行操作.由于结果也应该是否定的,我必须否定结果,以便再次获得正数.对于较大的BigIntegers,否定最多三个值可能是相当大的性能成本.

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

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

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

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

如果它们存在的话,我根本找不到任何与负值和按位运算相关的法则.因此我的问题.

Answer 1

Joh*_*ica 5

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

-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 用一个替换or

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

我们仍然需要not在最后做一个昂贵的,但因为不是如此接近-我们可以欺骗和替换昂贵not的便宜-,如此:

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

最后结果将是:

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

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

实施起来非常便宜,因为:

同样的事情or; not or非常接近and.