整数溢出与左移

我在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

整数溢出与左移

回答

相关问题