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

本文关键字：整数 溢出 左移 | 更新日期: 2023-09-27 18:20:06

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

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

对于某个整数n。

只要n小于5，我就会得到正确的答案。然而，对于n>=5，它不起作用。

使用逐位运算符，如何在n=5和n=6的情况下获得正确答案，有什么想法吗？对于n=6，结果应该为~0UL，对于n=5，结果应该是0xFFFFFFFF。

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

只要n小于5，我就会得到正确的答案。然而，对于n>=5，它不起作用。

嗯，它符合规范。来自C#5规范第7.9节：

<lt；操作员将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。

现在，如果按照p.s.w.g的建议，将"外部"移位运算符的第一个操作数设为1UL，则会遇到规范的这一部分：

  • 当x的类型是long或ulong时，移位计数由count的低位六位给出。换句话说，移位计数是根据count & 0x3F来计算的

因此，代码将按照您的预期执行，至少对于n=5，但对于n=6则不然。

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

问题是文字"1"是一个32位有符号整数，而不是64位无符号长整型。当n等于或大于5时，您超出了32位整数的范围。

将适当的1更改为1UL可以解决此问题，并且适用于n=5（但不适用于n=6，这超出了ulong的范围）。

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

让它在n=6时工作（即获得0xFFFFFFFFFFFFF）并不容易。一个简单的解决方案是使用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];
相关文章：