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 回答