2

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

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

对于某个整数 n。

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

任何想法，使用按位运算符，即使对于 n = 5 和 n = 6，如何获得正确答案？对于 n=6，结果应该是 ~0UL，对于 n=5，结果应该是 0xFFFFFFFF。

4

3 回答 3

12

只要 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-26T20:23:55.693 回答
5

我认为问题在于常量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-26T20:25:41.573 回答
4

问题是文字 '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-26T20:28:26.683 回答