CODEWITHSUNDEEP
javabigintegerbit-shift
Tapas Bose
Tapas Bose

Reputation: 29806

BigInteger unsigned left or right shift

I am reimplementing a function using BigInteger in place in int. Now there is step

h = n >>> log2n--

But I am facing trouble here. In original code h, n, log2n all are int type, if I set h, n, and log2n to BigInteger what will be the equivalent expression of the above code? How do I perform an unsigned right shift (>>>) in BigInteger?
Edit: The code block is :

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);
        }
    }

Upvotes: 3

Views: 5049

Answers (3)

Karsten Becker
Karsten Becker

Reputation: 510

I finally found a solution, it's awful, but it works:

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;
}

The case that your integer is positive is trivial, as shiftRight will return the correct result anyway. But for negative numbers this gets tricky. The negate version mentioned earlier does not work as -1 in BigInteger negated is 1. Shift it and you have 0. But you need to know what the width of your BigInteger is. You then basically force the BigInteger to have at least width+1 bits by subtracting an opener. Then you perform the shifting, and mask away the extra bit that you introduced. It doesn't really matter what opener you use, as long as it doesn't alter the lower bits.

How the opener works:

The BigInteger implementation does only store the highest 0 position for negative numbers. A -3 is represented as:

1111_1111_1111_1111_1101

But only some bits are stored, I marked the others as X.

XXXX_XXXX_XXXX_XXXX_XX01

Shifting to the right does nothing as there are always 1's coming from the left. So the idea is to substract a 1 to generate a 0 outside of the width that you are interested in. Assuming you care about the lowest twelve bit:

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

This forced the generation of real 1s. You then shift right by lets say 5.

XXXX_XXX0_1111_1111_1101
>>5   XXXX_XXX0_1111_111

And then mask it:

XXXX_XXX0_1111_111
0000_0000_1111_111

And therewith receive the correct result:

0000_0000_1111_111

So the introduction of the zero forced the BigInteger implementation to update the stored 0 position to a width that is higher than the one you are interested in and forced the creation of stored 1s.

Upvotes: 6

Jon Bright
Jon Bright

Reputation: 13738

Quoting from the Java docs:

The unsigned right shift operator (>>>) is omitted, as this operation makes little sense in combination with the "infinite word size" abstraction provided by this class.

An 32-bit integer representation of -1 is (in binary) 

11111111 11111111 11111111 11111111

If you use the signed right-shift operator (>>) on this, you'll get 

11111111 11111111 11111111 11111111

i.e. the same thing. If you use the unsigned right-shift operator on this, shifting by 1, you'll get 

01111111 11111111 11111111 11111111.

But BigInteger has an unlimited length. The representation of -1 in a BigInteger is theoretically 

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

The unsigned right-shift operator would imply that you were putting a 0 at the leftmost point - which is at infinity. Since this makes little sense, the operator is omitted.

As regards your actual code, what you need to do now depends on what the surrounding code is doing and why an unsigned shift was chosen for the original code. Something like 

n.negate().shiftRight(log2n)

might work, but it all depends on the circumstances.

Upvotes: 8

Mark Bakker
Mark Bakker

Reputation: 1348

The BigInteger class has the following operations

 BigInteger     shiftLeft(int n)

 BigInteger     shiftRight(int n)

Upvotes: 0

Related Questions