带左移的C#中的整数溢出

Question

我在C#中有以下代码行:

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

对于某些整数n.

只要n小于5,我就得到正确的答案.但是,对于n> = 5,它不起作用.

任何想法,使用按位运算符,即使n = 5和n = 6,如何得到正确的答案？对于n = 6,结果应为~0UL,对于n = 5,结果应为0xFFFFFFFF.

Answer 1

只要n小于5,我就得到正确的答案.但是,对于n> = 5,它不起作用.

嗯,它遵守规范.从C#5规范的第7.9节:

<<运算符将x向左移位如下所述计算的位数.

对于预定义的运算符,要移位的位数计算如下:

• 当类型x为int或时uint,移位计数由低位五位给出count.换句话说,移位计数是从count & 0x1F.

所以当n5是,1 << n(内移)是32.所以你有效地得到了:

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

现在32 & 0x1f是0 ...因此你有(1 << 0) - 10.

现在,如果你1UL按照pswg的建议制作"外部"移位运算符的第一个操作数,那么你就会遇到规范的这一部分:

• 当类型x为long或时ulong,移位计数由低位六位给出count.换句话说,移位计数是从count & 0x3F.

因此,代码将按照您的预期进行,至少对于n = 5 - 但不是n = 6.

Answer 2

我认为问题是常量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 }