BigInteger 无符号左移或右移

Question

我正在 int 中使用 BigInteger 重新实现一个函数。现在有步骤了

h = n >>> log2n--

，但我在这里遇到了麻烦。原始代码中h、n、log2n都是int类型，如果我将h、n、log2n设置为BigInteger，上面代码的等价表达式是什么？如何在 BigInteger 中执行无符号右移 (>>)？
编辑： 代码块是：

int log2n = 31 - Integer.numberOfLeadingZeros(n);
    int h = 0, shift = 0, high = 1;

    while (h != n)
    {
        shift += h;
        h = n >>> log2n--;
        int len = high;
        high = (h & 1) == 1 ? h : h - 1;
        len = (high - len) / 2;

        if (len > 0)
        {
            p = p.multiply(product(len));
            r = r.multiply(p);
        }
    }

Answer 1

引用Java文档：

无符号右移运算符
(>>>) 被省略，因为此操作
结合起来没有什么意义
“无限字长”抽象
由此类提供。

-1 的 32 位整数表示为（二进制）

11111111 11111111 11111111 11111111

如果对此使用有符号右移运算符 (>>)，您将得到

11111111 11111111 11111111 11111111 

相同的结果。如果您对此使用无符号右移运算符，移位 1，您将得到

01111111 11111111 11111111 11111111.

But BigInteger has an unlimited length。 BigInteger 中 -1 的表示理论上是

11111111 111... infinite 1s here..... 11111111

无符号右移运算符意味着您将 0 放在最左边的点 - 即无穷大。由于这没有什么意义，因此省略了该运算符。

至于您的实际代码，您现在需要做什么取决于周围代码正在做什么以及为什么为原始代码选择无符号移位。像这样的东西

n.negate().shiftRight(log2n)

可能有效，但这一切都取决于具体情况。

Answer 2

我终于找到了一个解决方案，它很糟糕，但它有效：

public BigInteger srl(BigInteger l, int width, int shiftBy) {
    if (l.signum() >= 0)
        return l.shiftRight(shiftBy);
    BigInteger opener = BigInteger.ONE.shiftLeft(width + 1);
    BigInteger opened = l.subtract(opener);
    BigInteger mask = opener.subtract(BigInteger.ONE).shiftRight(shiftBy + 1);
    BigInteger res = opened.shiftRight(shiftBy).and(mask);
    return res;
}

整数为正的情况是微不足道的，因为 shiftRight 无论如何都会返回正确的结果。但对于负数，这会变得棘手。前面提到的取反版本不起作用，因为 BigInteger 中的 -1 取反是 1。将其移位，得到 0。但是您需要知道 BigInteger 的宽度是多少。然后，您基本上可以通过减去开场符来强制 BigInteger 至少具有 width+1 位。然后执行移位，并掩盖您引入的额外位。使用什么开启器并不重要，只要它不改变较低的位即可。

开启器的工作原理：

BigInteger 实现仅存储负数的最高 0 位置。 -3 表示为：

1111_1111_1111_1111_1101

但只存储了一些位，我将其他位标记为 X。

XXXX_XXXX_XXXX_XXXX_XX01

向右移位没有任何作用，因为总是有 1 来自左侧。因此，我们的想法是减去 1 以在您感兴趣的宽度之外生成 0。假设您关心最低的 12 位：

XXXX_XXXX_XXXX_XXXX_XX01
-    0001_0000_0000_0000
========================
XXXX_XXX0_1111_1111_1101

这会强制生成真正的 1。然后向右移动，比如 5。

XXXX_XXX0_1111_1111_1101
>>5   XXXX_XXX0_1111_111

然后屏蔽它：

XXXX_XXX0_1111_111
0000_0000_1111_111

从而收到正确的结果：

0000_0000_1111_111

因此，零的引入迫使 BigInteger 实现将存储的 0 位置更新为比您感兴趣的宽度更高的宽度并强制创建存储的 1。

Answer 3

BigInteger类有以下操作

 BigInteger     shiftLeft(int n)

 BigInteger     shiftRight(int n)