BigInteger无符号左移或右移

Question

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

h = n >>> log2n--

但我在这里遇到了麻烦.在原始代码H,N,log2n都是整数类型,如果设置了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文档:

省略了无符号右移运算符(>>>),因为此操作与此类提供的"无限字大小"抽象相结合没有多大意义.

一个32位的整数表示-1是(二进制)

11111111 11111111 11111111 11111111

如果你使用这个签名的右移运算符(>>),你就会得到

11111111 11111111 11111111 11111111 

即同样的事情.如果你使用无符号右移运算符,换1,你就会得到

01111111 11111111 11111111 11111111.

但BigInteger的长度不受限制.理论上,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至少有宽度+ 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

这迫使真正的1s的产生.然后你转过来让我们说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.