关于C语言中的位掩码。为什么(~(~0 << N))比((1 << N) -1)更受欢迎？

Question

我知道在计算机中使用~0可以得到最大的位数为1的值（这也考虑了可移植性），但我仍然不明白为什么((1 << N) - 1)不被推荐使用？

如果您曾经使用第二种形式并遇到过问题，请分享一下。

- MS.

---

因为并非所有的C编译器/平台在处理负数时都使用二进制补码。 - jv42

你能提供一个不鼓励使用 ((1 << N) -1) 的来源吗？ - Juraj Blaho

@harold：问题在于如果你在1s' complement中执行unsigned int x = ~0;。~0是所有位都设置为1，作为有符号值表示负零（或者是一个陷阱表示）。因此，当它被转换为无符号值时，结果是0，而不是UINT_MAX。unsigned int x = ~0;不能处理可移植性，如果我们的意思是“包括非2的补码”。正确的方法是unsigned int x = -1;或unsigned int x = UINT_MAX;。 - Steve Jessop

@SteveJessop 谢谢您详尽的解释 :) - jv42

@harold：没错，但我不是在谈论二进制补码。在一个不支持负零的1s'补码实现中，~0 是未定义行为。因此，严格符合规范的代码不能写 ~0。不过，~0u 是可以的。对于带符号表示法中的原码，(1 << N) 和 1's补码中的~0一样糟糕，所以它们在有符号表示方面同样糟糕。 - Steve Jessop

Answer 1

看这些代码：

1. printf("%X", ~(~0 << 31) );
2. printf("%X", (1 << 31) - 1 );

第1行编译并表现正常。

第2行会提示警告信息：expression中的整数溢出。

这是因为默认情况下，1 << 31 被视为 带符号的 int 类型，所以 1 << 31 = -2147483648，也就是最小的可能整数。

因此，对1进行运算时会发生溢出。

- Dennis

---

你可以无需警告地执行 (1u << 31) - 1 。 - Juraj Blaho

@Juraj Blaho：是的，但这不是问题所在。((1 << N) - 1)根本行不通。 - Dennis

谢谢Dennis！是的，它确实会发出警告.. :) 但是当用作位掩码时，溢出仍然可以被忽略吗？ - MS.

@MS.：有符号整数的溢出是未定义行为，所以它可能会根据编译器而起作用或不起作用。GCC 会根据有符号整数不应溢出的事实进行激进的优化。 - Juraj Blaho

@R..说得很好，说明这个答案是完全错误的。编译器不警告1 << 31真是太可惜了。它是-2147483648只是一个巧合。如果int是32位宽，则1 << 31的结果在int中无法表示，这就是我们遇到的未定义行为。 - Jens Gustedt

Answer 2

第一个形式绝对不是首选，我甚至可以说它永远不应该被使用。在不支持负零的一元补码系统中， ~ 0 很可能是一个“trap representation”，因此在使用时会引发 UB。

另一方面， 1 << 31 也是 UB，假设 int 是 32 位，因为它会溢出。

如果你真的意思是常数 31， 0x7fffffff 是编写掩码的最简单和最正确的方法。如果你想要除了符号位以外的所有 int ， INT_MAX 是编写掩码的最简单和最正确的方式。

只要你知道 bitshift 不会溢出， (1 << n) - 1 就是生成具有最低 n 个位设置的掩码的正确方法。最好使用 （1ULL << n）-1 然后进行强制转换或隐式转换，以免担心带符号问题和移位溢出。

但无论你做什么，永远不要使用有符号整数的 ~ 运算符。

- R.. GitHub STOP HELPING ICE

---

我从未想到过'1 << 31是未定义行为。直到今天，我读过的所有文本都说明signed int可以取从-2147483648到2147483647的所有值，两者都包括在内。问题：#define INT_MIN (-2147483647 - 1)是否可以解决这个问题？我问这个问题是因为这就是gcc、tcc和icl中limits.h`所做的... - Dennis

signed int 可以取该范围内的所有值，与 1<<31 溢出无关。这只是一个算术问题。2^31 大于 INT_MAX（假设为 32 位 int），因此它会溢出。 - R.. GitHub STOP HELPING ICE

那么看起来我对位移操作的理解不够好。我曾经学过，1 << 31 而不是 2^31，是将 1 左移 31 位并在右侧填充 0。这将产生二进制的 10000000 00000000 00000000 00000000 或十六进制的 0x80000000，或带符号整数的 -2147483648。我错在哪里了？ - Dennis

在C语言中，x<<y只是算术运算x*2^y的简写。它与位移操作相对应只是一种巧合。 - R.. GitHub STOP HELPING ICE

@Lundin：这里讨论的是类型转换。这里没有进行任何转换。如果你使用了"1U<<31"，然后将其转换为“int”，那么行为将会是实现定义的，而不是未定义的。如果你使用了"(1U<<31)-1"，那么结果将在'int'范围内，因此转换将是良好定义的。 - R.. GitHub STOP HELPING ICE

Answer 3

我会不鼓励在有符号值上进行移位或补码操作，因为这只是一个坏主意。应该总是在无符号类型上产生位模式，然后（如果必要）转置到有符号的对应部分。使用原始类型也不是一个好主意，因为通常在位模式上，你应该控制你正在处理的位数。

所以我总是会做一些像这样的事情

-UINT32_C(1)
~UINT32_C(0)

这些是完全等效的，最终只需要使用UINT32_MAX等。

只有在您没有完全移位的情况下才需要移位，例如：

(UINT32_C(1) << N) - UINT32_C(1)

- Jens Gustedt

Answer 4

我不偏向于其中任何一个，但我见过许多使用(1<<N)的错误，其中值必须为64位，但“1”是32位（int为32位），并且对于N>=31，结果是错误的。使用1ULL而不是1可以解决这个问题。这就是这种移位的一个危险之处。

此外，将int左移CHAR_BIT*sizeof(int)或更多位置（类似地，将long long（通常为64位）左移CHAR_BIT*sizeof(long long)或更多位置）是未定义的。因此，像这样向右移位可能更安全：~0u>>(CHAR_BIT*sizeof(int)-N)，但在这种情况下，N不能为0。

- Alexey Frunze

---

~0 也有32位的问题吗？ - harold

@harold：如果int是32位，则0将为32位。但您指的是什么问题？哦，可以理解地，在`0u >>（CHAR_BIT * sizeof（int）-N）中，1 <= N <= CHAR_BIT * sizeof（int）`。您可以适当地将此表达式扩展到long-long。 - Alexey Frunze

我是说，它没有理由选择 (0 << N) 而不是 (1 << N) - 1。 - harold

@harold：我只是指出了我遇到的一些问题。需要注意一下。 - Alexey Frunze

Answer 5

编辑：更正了一个愚蠢的错误，并注意到可能存在溢出问题。

我从未听说过一种形式比另一种形式更受欢迎。两种形式都在编译时评估。我总是使用第二种形式，而且从来没有遇到任何麻烦。对于读者来说，这两种形式都非常清晰明了。

其他答案指出了第二种形式可能存在溢出的可能性。

我认为它们之间几乎没有什么区别。

- Pete Wilson

---

第一个如何在编译时评估，而第二个却不能？ - Juraj Blaho

Answer 6

为什么不建议使用
~0是一个单周期操作，因此更快 ((1<首先进行移位，然后进行减法，这是一种算术运算。由于减法，它将消耗大量的周期，因此会产生不必要的开销。

更多信息
而且，当你执行((1 << N)-1)或((M << N)-1)时，假设N指的是M的位数，因为它将刷新所有位。这里的1是整数，在几乎所有现有平台32/64位上都是32位，因此可以假定N为32。

但是，如果你将1强制转换为long并执行(((long)1 << 32) -1)，结果将不同。 在这里，你需要使用64代替32，因为64是long的位数。

- Abhinav

---

我也很想知道 ((1<<32)-1) 的转换是在编译时还是运行时完成的。 - Abhinav

我所知道的任何平台都不是这样的，但更重要的是，任何不完全愚蠢的编译器都将使用零指令并计算常量。 - harold

哈罗德：什么不是真的？<br>在1<<N中，1不会被视为int类型吗？ - Abhinav

既不用移位也不用减法将消耗大量周期。尽管在史前时代，超过1的移位曾经很慢。 - harold

@Juraj 不，我认为这没有意义。只有在移位实现使用常量时，~0和移位实现才是等效的。我不会期望整数中的位数在运行时变化... - Lundin