当左侧操作数为负值时，为什么左移操作会引发未定义行为？

Question

当左侧操作数为负值时，为什么左移操作会引发未定义行为？

c++clanguage-lawyerundefined-behaviorbit-shift

55

在C语言中，当左操作数为负值时，按位左移操作将会导致未定义的行为。

引用自ISO C99 (6.5.7/4):

E1 << E2 的结果是E1向左移动E2个二进制位，空出的位用0填充。如果E1的类型是无符号的，那么结果的值为E1乘以2的E2次方，然后对结果类型所能表示的最大值加1取余。如果E1是有符号类型并且非负，且E1乘以2的E2次方可以被结果类型所表示，则该值即为结果；否则行为未定义。

但在C++中，这种行为是定义明确的。

引用自ISO C++-03 (5.8/2):

E1 << E2的值就是将E1（解释为位模式）向左移动E2个二进制位，并用0填充空出的位。如果E1具有无符号类型，则结果的值为E1乘以2的E2次方，然后对ULONG_MAX+1取余（如果E1的类型是unsigned long），否则对UINT_MAX+1取余（注意：常量ULONG_MAX和UINT_MAX在头文件中定义）。

也就是说：

int a = -1, b=2, c;
c= a << b ;

在 C 中会触发未定义行为，但在 C++ 中该行为是被定义好的。

那么是什么促使 ISO C++ 委员会认为这种行为是好定义的呢？相比之下，当左操作数为负数时，位右移操作的行为是 “实现定义的”，对吗？

我的问题是，为什么左移操作会触发 C 中的未定义行为，而右移操作符只会引起“实现定义的”行为？

P.S：请不要给出像“这是未定义的行为，因为标准规定如此”这样的答案。:P

- Prasoon Saurav

10

C和C++是由不同委员会标准化的不同语言。我认为这并不令人惊讶。 - fredoverflow

2

此外，C++是基于C89/C90的。然后，C委员会朝着不同的方向发展了C99标准。C99和C++都是基于最初的C标准，但它们的差异并没有得到任何协调。 - David Thornley

4

你的 C++ 引用仅定义了无符号类型的行为。你是否忘记复制关于有符号值的段落了？ - R.. GitHub STOP HELPING ICE

4

@R.. 这段文本通过第一句定义了有符号的行为。然后通过其他句子进一步详细说明了无符号的行为。 - Johannes Schaub - litb

这是未定义行为，因为标准在5p5中如此规定。 - Ben Voigt

显示剩余2条评论

8个回答

22

在C中，当左侧操作数具有负值时，按位左移操作会引发未定义的行为。但在C++中，这种行为的定义是明确的。简单的答案是：因为标准规定如此。更长的答案可能与C和C ++都允许负数的其他表示方式有关，除了2的补码外，还可以使用其他方式。给出较少的保证使得可能在其他硬件上使用这些语言，包括晦涩和/或旧的机器。由于某种原因，C ++标准化委员会觉得需要添加一个有关位表示如何更改的小保证。但由于负数仍可以通过1的补码或符号+幅度来表示，所以所得到的值可能性仍然各不相同。假设16位整数，我们将有

 -1 = 1111111111111111  // 2's complement
 -1 = 1111111111111110  // 1's complement
 -1 = 1000000000000001  // sign+magnitude

左移3位后，我们会得到

 -8 = 1111111111111000  // 2's complement
-15 = 1111111111110000  // 1's complement
  8 = 0000000000001000  // sign+magnitude

ISO C++委员会为什么要考虑将这种行为视为定义良好的行为，而不是C中的行为？

我猜他们提供了这个保证，以便在你知道自己在做什么时（例如当你确定你的机器使用二进制补码时），可以适当地使用 <<。

另一方面，当左操作数为负数时，位右移操作的行为是实现定义的，对吗？

我得检查一下标准。但你可能是对的。在二进制补码机器上进行无符号扩展的右移操作并不特别有用。因此，当前状态肯定比要求空出的位填充为零要好，因为它留下了进行符号扩展的机器的余地 - 即使这不能得到保证。

- sellibitze

编写标准的一个目标是尽可能地确保，如果任何实现在某种情况下执行了有用的操作，则允许符合规范的实现以类似的方式行事。在超出标准管辖范围的情况下，实现可能有用地陷入陷阱的情况被标记为调用未定义行为。C标准的作者可以想象，一些实现在左移至少一些负值时可能会陷入陷阱，并且某人可能会发现这很有用，因此该行为被留作未定义。 - supercat

一些现有的实现在右移时填充零，而另一些则进行符号扩展。由于一些为前者实现编写的代码可能依赖于该行为，因此它被留作实现定义。我认为当C++委员会意识到左移负值时可能会导致某些平台陷入困境时，他们修复了左移行为，但实际上没有任何平台这样做，允许未来的实现开始这样做并没有任何好处。 - supercat

7

针对标题中实际的问题，就像对任何有符号类型的操作一样，如果数学运算的结果超出了目标类型的范围（下溢或上溢），这将导致未定义的行为。有符号整数类型就是这样设计的。

对于左移操作，如果值为正数或0，则将运算符定义为2的幂次方乘法是有意义的，因此一切都没问题，除非结果溢出，这并不奇怪。

如果值为负数，你也可以将其解释为乘以2的幂次方，但如果你只考虑位移，那么这可能会令人惊讶。显然，标准委员会希望避免这种歧义。

我的结论：

- 如果你想进行真正的位模式操作，请使用无符号类型。 - 如果你想将一个值（有符号或无符号）乘以2的幂次方，请直接这样做，例如 i * (1u << k)。你的编译器无论如何都会将其转换为合适的汇编代码。

- Jens Gustedt

将二进制补码数的符号位设置为1，相当于在左侧设置无限多个1。32位数字中可表示的值是那些31位左侧所有位都具有相同值的值。负的二进制补码值进行移位操作并没有什么异常或反常之处，除非存在超过符号位的值，其状态与符号位不匹配。 - supercat

3

这些操作通常需要在普通的CPU指令支持范围内进行平衡，同时又要有足够的实用性，以便于编译器能够保证即使需要额外指令也能够实现。一般来说，程序员使用位移操作符时期望它们能够映射到具有这种指令的CPU上的单个指令，因此存在未定义或实现行为，其中各种处理“边缘”条件的CPU处理方式不同，而不是规定一个行为并使操作变得意外缓慢。请注意，即使对于更简单的用例，也可能需要添加额外的前/后处理指令。在某些CPU生成陷阱/异常/中断（与C++ try/catch类型异常不同）或通常无用/难以解释的结果的情况下，未定义的行为可能是必要的，而如果标准委员会当时考虑的CPU集合都提供了至少一些定义行为，则可以将行为定义为实现定义。

- Tony Delroy

据我所知，在某些CPU上，左移N指令将执行N次移位。如果N是一个长整型，它的值为-1，那么需要大约40亿个周期才能完成。一条通常只需要几微秒的指令却会让CPU锁定数分钟，这足以被视为“未定义行为”，而不仅仅是说该值是“实现定义的”，特别是因为让一条指令执行那么长时间可能会导致看门狗重置CPU。 - supercat

1

感谢虚拟操作规则，编译器只需在这种架构上添加与数字位数相同的移位指令。因此，对于64位数字，最多可以实现64次移位（或将其设置为0或向上移位至63，具体取决于编译器选择实现方式）。 - David Stone

很不幸，自您写上述内容以来，情况已经发生了变化。即使在使用具有左移指令的处理器时，该指令的行为与二进制补码算术完全一致，超现代编译器哲学也认为这并不是让这种左移行为遵守时间和因果律的理由。现代哲学规定，对于 if (x >= 0) launch_missiles(); x<<=1; 这样的代码，编译器应该意识到如果 x 是负数，它可以无条件地发射导弹，因此可以随意进行任何操作。 - supercat

就我个人而言，我发现这种超现代的想法令人不安；一个只处理最多63个并且在超出范围后会掉落的跳转表的情况可能是一个合理的借口，但掩盖最坏情况下只会增加一条指令，即使在最好的情况下也需要4-5条指令序列。 - supercat

1

我的问题是为什么在C语言中左移操作会引起未定义行为，而右移操作只会引起实现定义的行为？

LLVM的工作人员推测，位移运算符之所以有限制，是因为它在不同平台上的指令实现方式不同。来自What Every C Programmer Should Know About Undefined Behavior #1/3的引述如下：

“... 我猜这是由于各种CPU上的底层移位操作对此做出了不同的处理：例如，X86将32位移位量截断为5位（因此32位移位相当于0位移位），但PowerPC将32位移位量截断为6位（因此32位移位产生零）。由于这些硬件差异，行为在C中完全未定义...”

请注意，讨论的是移位量大于寄存器大小的情况。但这是我从权威机构找到的最接近解释移位限制的内容。

我认为第二个原因是在2的补码机器上潜在的符号变化。但我从未在任何地方读到过（不冒犯@sellibitze（我碰巧同意他的观点））。

- jww

你似乎在讨论右侧操作数的符号性；但问题只涉及左侧操作数。 - Ben Voigt

1

在C89标准下，在未使用填充位的有符号和无符号整数类型上，左移负值的行为已经明确定义。有符号和无符号类型共同拥有的值位必须在相同的位置，有符号类型的符号位只能与无符号类型的最高位值位相同，而该值位只能在其他所有位的左侧。

C89规定的行为对于没有填充位的二进制补码平台是有用和合理的，至少在将它们视为乘法不会导致溢出的情况下如此。该行为可能在其他平台或旨在可靠地捕获有符号整数溢出的实现中并不理想。 C99的作者可能希望在C89规定的行为不太理想的情况下允许实现灵活性，但是在没有强烈理由要求否则的情况下，文本中没有暗示优质实现不应继续以旧方式运作的意图。

很不幸，尽管没有任何实现C99的使用非二进制补码的情况，但C11的作者拒绝定义常见情况（未溢出）的行为; 我记得，理由是这样做会妨碍“优化”。当左操作数为负数时，将左移操作符调用未定义的行为使编译器可以假定只有在左操作数为非负数时才能到达该移位。

我对这种优化有多少真正有用表示怀疑，但这种实用性的罕见性实际上有利于保持行为未定义。如果唯一的情况是在这种情况下优化实际上是有用的，而如果实际上不存在这样的情况，则实现无论是否有要求都将以普通方式行事，并且不需要强制执行该行为。

- supercat

但是正是return x<<4;这一行会触发UB，编译器几乎无法改变该行之前代码的明确定义语义。我使用了-O2和-O3进行了测试，至少gcc没有执行您建议的优化。 - Björn Lindqvist

@BjörnLindqvist：目前的gcc主线版本在死代码消除方面不如标准允许的那么积极，但标准中添加了语言，明确规定如果使用给定输入执行代码将导致未定义行为，则即使在UB发生之前，标准也不对程序的任何行为施加要求。个人认为，如果现在的大多数UB受到足够限制，那么标准会更好，这样就可以编写满足要求的程序... - supercat

（1）当给定有效输入时，产生有效输出；（2）即使在给定无效输入的情况下，也要遵守时间和因果律的规则，以满足这样的要求，即使发生算术溢出等情况，但标准并不强制执行此类要求。 - supercat

@BjörnLindqvist：只要编译器能确定输入将导致未定义行为（UB），它就可以开始做任何它想做的事情。允许UB在某种程度上豁免于“时间”法则是合理的，因为这样可以使编译器在不必先验证它们是否会触发溢出的情况下，执行类似提升循环不变表达式的操作。然而，标准的语言并没有限制编译器“利用”未定义行为的程度，一些作者试图最大化这样的机会。 - supercat

根据我所读的内容，左移负数最初被定义为未定义行为，以便允许可能存在某台机器会触发陷阱的可能性；鉴于没有证据表明这样的机器曾经存在过，委员会考虑更改规范，使其仅产生未指定的值，但编译器作者反对该变更，称它会“妨碍优化”。我的回答可能过于尖刻，但考虑到编译器研究人员正在寻找修剪代码的方法，这是... - supercat

只有在代码调用未定义行为（Undefined Behavior）的情况下，才会相关。对于某些形式的未定义行为可能有用，但对于其他形式则毫无帮助。我理解他们希望保持负值左移的未定义状态，是因为他们希望让编译器假设将要进行左移的值永远不会是负数，并省略任何仅与将要进行左移的负数值相关的代码。 - supercat

0

C++03的行为与C++11和C99相同，您只需要超越左移规则即可。

标准的第5p5节说：

如果在表达式的评估过程中，结果在数学上没有定义或不在其类型的可表示值范围内，则行为是未定义的

在C99和C++11中特别指出的左移表达式是未定义行为，它们都会计算出一个超出可表示值范围的结果。

实际上，关于无符号类型使用模运算的句子是专门为了避免生成超出可表示范围的值，这将自动成为未定义行为。

- Ben Voigt

在二进制补码表示法中，-1的位表示为...111[111].000...，计算机通常只存储中间部分，将MSB复制到左侧，并用零填充右侧；将其向左移动一位应该得到...111[110].000...即-2。在一进制补码表示法中，-1为...111[110].111...，计算机存储中间部分并在两侧重复最左边的位。将其向左移动一位应该得到...[101].111...，即-2，尽管某些实现可能会移入零而不是重复符号位。 - supercat

无论如何，任何操作的结果都应该在指定类型的范围内。只有在符号-幅度系统中才可能存在真正的问题。 - supercat

-2

移位的结果取决于数字表示法。只有当数字表示为二进制补码时，移位才像乘法一样运作。但问题并不仅限于负数。考虑一个用过量8（又称偏移二进制）表示的4位带符号数。数字1表示为1+8或1001。如果我们将其左移为位，我们得到0010，这是-6的表示形式。同样，-1表示为-1+8，即0111，左移后变成+6的表示形式1110。按位行为是明确定义的，但数字行为高度依赖于表示系统。

- Reality Pixels

我看到这篇文章收到了几个负面评价。我认为这是由于规范中的声明与之冲突：“E1 << E2 的值是将 E1 左移 E2 位；空出的位将填充零。如果 E1 具有无符号类型，则结果的值为 E1 × 2E^2 ....”。Excess-N 表示法没有这个属性。这意味着 C/C++ 不能在这样的机器上按照规范实现。 - Reality Pixels

在C89标准下，你的说法是正确的。然而，在C99标准中，同时增加了一个明确的声明，即左移负值会产生未定义行为，并且在64位或更少字长的机器上禁止除二进制补码实现以外的任何操作（据我所知，非人为构造的非二进制补码C99实现数量为零）。 - supercat

@Prasoon Saurav 这不是符合 C++20 标准的正确答案吗？ - Glenn Teitelbaum

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Yakov Galka · Accepted Answer

您复制的段落涉及无符号类型。在C++中，其行为是未定义的。来自最新的C++0x草案：“E1 << E2”的值是将E1左移E2个位位置；空出的位用零填充。如果E1具有无符号类型，则结果的值是E1 × 2的E2次方，对比结果类型可表示的最大值多余一的模数减小。否则，如果E1具有带符号类型并且非负值，并且E1×2的E2次方可以表示为结果类型，则这就是结果值; 否则，其行为是未定义的。”编辑：查看了C++98文件。它根本不提到带符号类型。因此仍然是未定义行为。右移负数是实现定义的，为什么？在我看来，这很容易被实现定义，因为没有从左侧截断问题。当您向左移动时，您必须说清楚不仅从右侧移动了什么，还要说明其他位的情况，例如使用二进制补码表示，这是另一个故事。