符号大小大整数的按位运算
Bitwise operations on sign-magnitude big integers
我正在 Delphi 中编写一个简单的 BigInteger 类型。这种类型由一组无符号 32 位整数(我称它们为四肢)、一个计数(或大小)和一个符号位组成。数组中的值被解释为绝对值,因此这是一个符号量级表示。这有几个优点,但也有一个缺点。
and
、or
、xor
和 not
等位运算具有二进制补码语义。如果两个 BigInteger
都具有正值,这没有问题,但是负数 BigInteger
的大小必须通过取反转换为二进制补码。这可能是一个性能问题,因为如果我们这样做,比如
C := -A and -B;
那么在执行and
操作之前,我必须否定A
和B
的量级。由于结果也应该是负数,因此我也必须否定结果才能再次获得正数。对于较大的 BigInteger
s,最多否定三个值可能会导致相当大的性能成本。
请注意,我知道该怎么做并且结果是正确的,但我想避免由大数组的必要否定引起的缓慢。
我知道一些快捷方式,例如
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 and/or -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 就可以替换 and not
or
not(-A and -B) = not(not(A - 1) and not(B - 1)) =
(A - 1) or (B - 1)
我们最后还需要做一个昂贵的not
,但是因为不是很接近-
我们可以欺骗并用便宜的[=替换昂贵的not
17=] 像这样:
-(-A and -B) = (A-1) or (B-1) + 1;
最后的结果是:
(-A and -B) = -((A-1) or (B-1) + 1);
这应该比翻转所有位要快得多。
这实现起来非常便宜,因为:
- 否定是对符号字节进行简单的位翻转。
- +1/-1 很快就会从 carry/borrow 位中 运行 位中压倒性的数量(只有 1/2^32 的情况会 carry/borrow 到下一个肢体).
or
也是如此; not or
非常接近 and
。
My question is: are there similar laws I can use to avoid negating the
magnitudes of "negative" BigIntegers?
是的,我在你想做的之前做了 - 请参阅 here,第 105 - 115 行(或者最好下载存储库)。奇怪的是我还用了“肢体”这个词。
例如 arrAndTwoCompl
计算正数和负数的按位 and
,arrAndTwoCompl2
计算 2 个负数的按位 and
。
我从 GMP 资源中获取了这些 'laws'。
不要重新发明大整数,只需使用它们。
我正在 Delphi 中编写一个简单的 BigInteger 类型。这种类型由一组无符号 32 位整数(我称它们为四肢)、一个计数(或大小)和一个符号位组成。数组中的值被解释为绝对值,因此这是一个符号量级表示。这有几个优点,但也有一个缺点。
and
、or
、xor
和 not
等位运算具有二进制补码语义。如果两个 BigInteger
都具有正值,这没有问题,但是负数 BigInteger
的大小必须通过取反转换为二进制补码。这可能是一个性能问题,因为如果我们这样做,比如
C := -A and -B;
那么在执行and
操作之前,我必须否定A
和B
的量级。由于结果也应该是负数,因此我也必须否定结果才能再次获得正数。对于较大的 BigInteger
s,最多否定三个值可能会导致相当大的性能成本。
请注意,我知道该怎么做并且结果是正确的,但我想避免由大数组的必要否定引起的缓慢。
我知道一些快捷方式,例如
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 and/or -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 就可以替换 and not
or
not(-A and -B) = not(not(A - 1) and not(B - 1)) =
(A - 1) or (B - 1)
我们最后还需要做一个昂贵的not
,但是因为不是很接近-
我们可以欺骗并用便宜的[=替换昂贵的not
17=] 像这样:
-(-A and -B) = (A-1) or (B-1) + 1;
最后的结果是:
(-A and -B) = -((A-1) or (B-1) + 1);
这应该比翻转所有位要快得多。
这实现起来非常便宜,因为:
- 否定是对符号字节进行简单的位翻转。
- +1/-1 很快就会从 carry/borrow 位中 运行 位中压倒性的数量(只有 1/2^32 的情况会 carry/borrow 到下一个肢体).
or
也是如此; not or
非常接近 and
。
My question is: are there similar laws I can use to avoid negating the magnitudes of "negative" BigIntegers?
是的,我在你想做的之前做了 - 请参阅 here,第 105 - 115 行(或者最好下载存储库)。奇怪的是我还用了“肢体”这个词。
例如 arrAndTwoCompl
计算正数和负数的按位 and
,arrAndTwoCompl2
计算 2 个负数的按位 and
。
我从 GMP 资源中获取了这些 'laws'。
不要重新发明大整数,只需使用它们。