BigInteger無符號左移或右移

我在int中使用BigInteger來重新實現一個函數。現在有步驟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); 
     } 
    }

來源

2011-03-12 Tapas Bose

你知道Java沒有運算符重載，對不對？ – 2011-03-12 10:07:09

是的。我不是說操作符重載。沒有找到無符號移位操作的轉向方法或方法或算法嗎？ – 2011-03-12 10:09:40

從Java文檔引用：

無符號的向右移位運算（>>>）被省略，因爲該操作與這個類提供的「無限字大小」抽象。

-1的32位整數表示（二進制）

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)

威力工作的東西，但是這一切都取決於具體情況。

來源

2011-03-12 10:18:25

+1符號位分開存儲。 – Margus 2011-03-12 10:24:34

這不回答問題 – 2015-12-01 08:28:08

BigInteger類具有以下操作

BigInteger  shiftLeft(int n) 

BigInteger  shiftRight(int n)

來源

2011-03-12 10:14:12

shiftRight和unsigned right shift是一樣的嗎？ – 2011-03-12 10:17:31

@Tapas：不，他們不是，查看Javadocs的BigInteger類。 – posdef 2011-08-27 10:52:37

我終於找到了解決辦法，這太可怕了，但它的工作原理：

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

這迫使真正的'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。

來源

2013-04-12 14:11:01

fyi這個問題被問及2年前回答並接受了一個答案 – tgkprog 2013-04-12 14:27:36

我還是不明白爲什麼你從l中減去一些2 ^（width + 1）。僅僅移位然後掩蓋新的位是不夠的？ – 2015-12-01 08:50:02

我添加了一些解釋，這有助於你嗎？ – 2015-12-01 13:06:06

BigInteger無符號左移或右移

回答

相關問題