BigInteger без знака левый или правый сдвиг - PullRequest
Новая
       15

BigInteger без знака левый или правый сдвиг

2 голосов
/ 12 марта 2011

Я переопределяю функцию, используя BigInteger вместо int.Теперь есть шаг 

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

Ответы [ 3 ]

7 голосов
/ 12 марта 2011

Цитирование из документов Java:

Оператор правого сдвига без знака (>>>) опущено, так как эта операция имеет мало смысла в сочетании с абстракция "бесконечного размера слова" предоставляется этим классом.

32-разрядное целочисленное представление -1 (в двоичном формате) 

11111111 11111111 11111111 11111111

Если вы используете подписанный оператор правого сдвига (>>) для этого, вы получите 

11111111 11111111 11111111 11111111

т.е. тоже самое. Если вы используете беззнаковый оператор правого смещения, сдвигая на 1, вы получите 

01111111 11111111 11111111 11111111.

Но BigInteger имеет неограниченную длину. Представление -1 в BigInteger теоретически 

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

Оператор правого сдвига без знака будет означать, что вы ставили 0 в крайнюю левую точку, то есть в бесконечность. Поскольку в этом нет особого смысла, оператор опущен.

Что касается вашего реального кода, то, что вам нужно сделать сейчас, зависит от того, что делает окружающий код, и почему для исходного кода было выбрано беззнаковое смещение. Что-то вроде 

n.negate().shiftRight(log2n)

может работать, но все зависит от обстоятельств.

5 голосов
/ 12 апреля 2013

Я наконец нашел решение, это ужасно, но оно работает: 

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 в любом случае вернет правильный результат.Но для отрицательных чисел это становится сложно.Упомянутая ранее версия отрицания не работает, так как -1 в BigInteger отрицается как 1. Сдвиньте ее, и вы получите 0. Но вам нужно знать, какова ширина вашего BigInteger.Затем вы в основном заставляете BigInteger иметь по крайней мере ширину + 1 бит, вычитая сошник.Затем вы выполняете сдвиг и маскируете лишний бит, который вы ввели.На самом деле не имеет значения, какой сошник вы используете, если только он не изменяет младшие биты.

Как работает сошник:

Реализация BigInteger хранит только самую высокую позицию 0для отрицательных чисел.-3 представлен как: 

1111_1111_1111_1111_1101

Но только некоторые биты сохранены, остальные помечены как X. 

XXXX_XXXX_XXXX_XXXX_XX01

Сдвиг вправо ничего не делает, так как всегда есть 1идет слева.Таким образом, идея состоит в том, чтобы вычесть 1, чтобы сгенерировать 0 за пределами ширины, которая вас интересует. Предполагая, что вы заботитесь о младшем двенадцатом бите: 

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 до ширины, превышающей ту, которая вас интересует, и принудительно создало сохраненные единицы.

0 голосов
/ 12 марта 2011

Класс BigInteger имеет следующие операции 

 BigInteger     shiftLeft(int n)

 BigInteger     shiftRight(int n)
...