0

我正在通过将一些 C++ 函数移植到 .NET 的 BigInteger 来独立研究位移。我注意到当我移动 BigInteger 时,空白被填充了。

我相信这与以二进制补码形式存储的负数有关。

BigInteger num = -126;
compactBitsRepresentation = (uint)(int)(num << 16);

这是移位后发生的事情(首先是最高有效位)

10000010 will be shifted 16
11111111100000100000000000000000 was shifted 16

我是否应该总是期望类似的位移操作以这种方式起作用?这是否与 OpenSSL 等“bigNumber”的不同语言和实现一致?

4

3 回答 3

1

来自BigInteger.LeftShift运营商文档

与整数基元的按位左移操作不同,LeftShift 方法保留原始 BigInteger 值的符号。

所以.NET 保证你看到的行为。

我对 bignum 库不太熟悉,但 OpenSSL 的 BIGNUM BN_lshift() 函数的文档说:

BN_lshift()将 a 左移 n 位并将结果放入 r ("r=a*2^n")。BN_lshift1()将 a 左移 1 并将结果放入 r ("r=2*a")。

由于该操作是根据乘以 2 的幂来定义的,如果将生成的 BIGNUM 转换为二进制补码(我不知道 BIGNUM 如何在内部表示数字),那么您将看到与 .NET 类似的行为。

如果其他 bignum 库的行为类似,我不会感到惊讶,但如果你想依赖这种行为,你真的需要检查文档。但是,由于移位与乘以或除以 2 的幂非常相似,因此您可以通过使用适当的乘法或除法而不是移位来获得“可移植”行为。那么您需要确保的就是您可以转换为二进制补码表示(这是一个真正独立于移位操作行为的问题)。

于 2013-03-11T00:07:08.943 回答
1

我是否应该总是期望类似的位移操作以这种方式起作用?

如果有问题的数字格式使用二进制补码来表示负数(很多都这样做),您应该这样做。为了形成一个数字的二进制补码,您将所有位反转并加一,例如:

23 is represented as 00010111
-23 is represented as 11101001 (that is, 11101000 + 1)

此外,当您将一个类型转换为更大的类型时,该值通常是符号扩展的,即最左边的位被扩展为更大类型中的额外位。这保留了数字的符号。

所以是的,数字表示用 1 来“填充”数值是很常见的。

于 2013-03-11T00:45:17.480 回答
0

首先将 10000010 更改为更大的宽度。在这种情况下,4 个字节:

10000010 --> 11111111 11111111 11111111 10000010

因为数字是负数,所以你在左边得到 1。

现在左移只需从右侧插入 0 并从左侧抛出位:

11111111 11111111 11111111 10000010 << 16 -->
11111111 10000010 00000000 00000000
于 2013-03-11T00:00:22.450 回答