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

Question

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

h = n >>> log2n-- 

Но я столкнулся с проблемой здесь. В исходном коде h, n, log2n все являются int-типом, если я устанавливаю h, n и log2n в BigInteger, что будет эквивалентным выражением вышеуказанного кода? Как выполнить беззнаковый сдвиг вправо (>>>) в BigInteger?
Edit: Блок код:

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 

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

01111111 11111111 11111111 11111111. 

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

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

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

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

n.negate().shiftRight(log2n) 

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

Answer 2

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

BigInteger  shiftLeft(int n) 

BigInteger  shiftRight(int n) 

Answer 3

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

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 

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

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-е.