整數溢出與左移

我在C＃下面的代碼行：n爲整數整數溢出與左移

ulong res = (1<<(1<<n))-1;

。

只要n低於5，我就可以得到正確的答案。但是，對於n> = 5，它不起作用。

任何想法，使用按位運算符，即使對於n = 5和n = 6，如何得到正確答案？對於n = 6，結果應該是〜0UL，對於n = 5，結果應該是0xFFFFFFFF。

來源

2013-06-26 user1448926

定義「它不工作」請 – tnw

（請注意，你的代碼甚至不進行編譯，順便說一句 - 有一個從'int'到'ulong'的隱式轉換。） –

事實上，我的最終版本是'（1UL（<< 1 << n）） - 1'，實際上它對n = 5起作用，但對於n = 6起作用。 Jon Skeet給出了我正在尋找的解釋。 – user1448926

只要n低於5，我就可以得到正確的答案。但是，對於n> = 5，它不起作用。

那麼，它服從規範。從C＃5規範的第7.9節開始：

< <運算符將x左移瞭如下所述計算的位數。

對於預定義的運算符，比特移位的數目計算如下：

當x類型是int或uint，移位計數被通過低順序給出的count五個位。換句話說，移位計數從count & 0x1F計算。

所以當n是5，1 << n（內移）爲32。所以，你然後得到有效：

int x = 32; 
ulong res = (1 << x) - 1;

現在32 & 0x1f是0 ...因此你必須(1 << 0) - 1這是0.

現在，如pswg所建議的那樣，如果將「外部」移位運算符1UL的第一個操作數作爲參考，則可以運行到規範的這部分：

當x類型是long或ulong，移位計數由低階的count六個比特給出。換句話說，移位計數從count & 0x3F計算。

因此，代碼會做，因爲它似乎你期望，至少對於n = 5 - 但不是對於n = 6

來源

2013-06-26 20:23:55

謝謝。這是我正在尋找的解釋。所以對於n = 6，我必須明確地返回〜0UL，而不是依靠<<的計算。 – user1448926

@ user1448926：是的，沒錯。 –

我相信問題是恆定的1被認爲是System.Int32所以它假定你想要操作的數據類型，但它很快溢出了該數據類型的界限。如果您將其更改爲：

ulong res = (1ul<<(1<<n))-1;

它爲我的作品：

var ns = new[] { 0, 1, 2, 3, 4, 5, 6 }; 
var output = ns.Select(n => (1ul<<(1<<n))-1); 
// { 0x1ul, 0x3ul, 0xful, 0xfful, 0xfffful, 0xfffffffful, 0ul }

來源

2013-06-26 20:25:41

謝謝。它適用於n = 5，但不適用於n = 6，因爲我想〜0ul而不是0ul。 – user1448926

@ user1448926我不認爲你可以用這種方法做到這一點，因爲在從值中減去1之前，你總是會遇到溢出。你必須使用* Strilanc *的'Bigint'或數組方法，或者嘗試以'〜0ul'開始並右移。 –

的問題是，字面「1」是一個32位有符號整數，而不是64位無符號長。當n等於或大於5時，超出了32位整數的範圍。

更改適當的1到1UL可以解決問題，並且適用於n = 5（但不是n = 6，它超出了ulong的範圍）。

ulong res = (1UL<<(1<<n))-1;

讓它工作n = 6（即得到0xFFFFFFFFFFFFFFFF）並不容易。一個簡單的解決方案是使用BigInteger，它將消除64位整數沒有定義的位移64位整數的問題。

// (reference and using System.Numerics) 
ulong res = (ulong)(BigInteger.One<<(1<<n)-1)

但是，這不會特別快。也許是一個常量的數組？

var arr = new[] {0x1, 0x3, 0xF, 0xFF, 0xFFFF, 0xFFFFFFFF, 0xFFFFFFFFFFFFFFFF}; 
ulong res = arr[n];

來源

2013-06-26 20:28:26

整數溢出與左移

回答

相關問題