我正在使用Delphi编写一个简单的BigInteger类型。这种类型由无符号32位整数数组(我称之为“limbs”)、计数(或大小)和符号位组成。数组中的值被解释为绝对值,因此这是一种符号-幅度表示法。这有几个优点,但也有一个缺点。
按位操作如“and”、“or”、“xor”和“not”具有二进制补码语义。如果两个BigInteger都具有正值,则没有问题,但负的BigInteger的幅度必须通过取反转换为二进制补码。这可能会导致性能问题,例如:
按位操作如“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 !=
不是真的,但也许有类似的东西?
我根本找不到与负值和按位操作相关的法律,如果它们存在的话。因此我的问题。