既然b始终不为零，为什么 `b ? --b : ++b` 可以工作，而 `--b` 不行？

Question

我试图使用递归来乘两个整数，但不小心写出了这段代码：

//the original version
int multiply(int a, int b)
{
  if ( !b )
     return 0;
  else
     return a + multiply(a, b ? --b : ++b ); //accident
}

我原本想写的是：b > 0 ? --b : ++b，但因疏忽写成了b ? --b : ++b。

我意识到我本来想写的行不通。但令我惊奇的是，我 没有 所意图写出的却可以运行。

现在，我注意到b ?--b : ++b与--b基本等价，因为else-block中的b保证为非零。所以我修改了上述代码，用--b替换了b?--b:++b，如下所示：

//the modified version
int multiply(int a, int b)
{
  if ( !b )
     return 0;
  else
     return a + multiply(a, --b); //modification here
}

由于原始版本可行，我期望修改后的版本也能够起作用。但是令我惊讶的是，它不起作用！

• 修改后的版本出了什么问题？
• 它与原始版本不等价吗？
• 如果b为非零值，--b不等价于b ?--b : ++b吗？如果等价的话，为什么第一个代码可以工作而第二个代码不行？

注意：这里的“起作用”是指它给出了正确的输出。也就是说，它给出了传递给函数的整数的乘积。

- Nawaz

---

等等！你能否定义一下“work”和“doesn't work”，这样我们就不需要去猜测你的算法在做什么了？ - Oliver Charlesworth

我不明白为什么最后一种情况会让人惊讶，如果 b 一开始就是负数，那么结果就是一个 SO。 - Nim

总的来说，我认为这不是一个特别好的问题。通过添加一些printf语句，可以轻松回答这个问题。（顺便说一下，我在第一个示例中得到了一个seg-fault错误。） - Oliver Charlesworth

除了其他人所说的之外，我没有看到你为什么要执行 --b/++b。没有理由修改本地变量。只需执行 b-1 和 b+1 即可完成操作。 - Sven

堆栈溢出了。ideone 也是如此神奇，它 DWIMified 了代码吗？ - David Hammen

Answer 1

它不起作用。我不知道ideone在搞什么鬼，那段代码将会溢出堆栈。

编辑

在gcc 4.6.0上尝试- segfault（由于堆栈溢出）。然而，如果您启用-O2 优化，那么“它工作”。总之：它的工作是偶然的，取决于编译器在幕后所做的事情。

g++ -g -Wall -o f f.cpp # stack overflow
g++ -O2 -g -Wall -o f f.cpp # "works"

- cnicutar

---

@rubenvb：对我来说，这似乎不是编译器的错误！ - Oliver Charlesworth

@Oli：从技术上讲，程序是格式良好的，然后从技术上讲，优化不能改变运行程序的结果，对吧？当然，代码本身有缺陷，但优化仍会改变结果。或者我想错了吗？ - rubenvb

在我看来，优化器在这里失败了，并且这加强了我的观点（不仅是我的观点，NASA和DoD在某些情况下禁止使用优化），即优化可能是一个非常糟糕的想法。我同意“它不起作用”的观点。 - David Hammen

@Ben：是的，你说得对，这不是真正的尾调用。@David：为什么你会说“优化器在这里失败了”？ - Oliver Charlesworth

@David：（回复晚了，没有看到你的评论）在这种特殊情况下，确实涉及到未定义的行为。但这是一个误导，可以轻易地发明一个等价的、定义明确的例子（基于无符号整数，例如），它仍然可能导致堆栈溢出或不会，这取决于编译器选择的优化方式。有理由不信任优化器，但这不是其中之一！ - Oliver Charlesworth

Answer 2

TL;DR版本: b? --b: ++b打印结果且--b失败并出现SIGXCPU的原因是ideone对提交的代码设置了时间限制。其中一种版本被更好地优化，并在允许的时间内完成。另一个版本给出完全相同的答案，但是你在ideone上看不到这个结果，因为它运行得太慢并被时间限制终止。

---

至于为什么没有发生栈溢出，我想在某种情况下编译器必须将递归转换为迭代（这不是尾调用，但易于转换）。

转换的结果可能类似于http://ideone.com/AeBYI，该代码确实给出了正确的结果。 使用更高的优化设置，编译器可以在编译时计算结果并在生成的代码中存储常量。

- Ben Voigt

---

是的，但那并没有回答问题。 - Karel Petranek

即使没有发生栈溢出，它怎么会给出正确的结果呢？它必须迭代几乎所有32位数字，并为每个数字添加12到结果中。在所有溢出之后，最终结果似乎不可能是正确的。 - Karel Petranek

@Ben：实际上，我的帖子中有一个错别字。请看一下，不是那个问题。而是 --b 与 b?--b:++b。两者都是相同的。但一个有效，另一个无效。 - Nawaz

@Nawaz：两种方法都可以。只是其中一种运行速度更快，因为编译器预先计算了结果。 - Ben Voigt

@Ben：这很有说服力。 :-) - Nawaz

Answer 3

下面代码的输出应该给出一个非常强烈的线索 ;)

#include <iostream>

using namespace std;

int multiply(int a, int b)
{
  cout << "a = " << a << "\tb = " << b << std::endl;
  if ( !b )
     return 0;
  else
     return a + multiply(a, b ? --b : ++b );
}

int main() {
        cout << multiply(12, 7) << endl;
        cout << multiply(12, -7) << endl;
        cout << multiply(-12, -7) << endl;
        cout << multiply(-12, 7) << endl;
        return 0;
}

It looks to me like it's getting the answer by going the long way.

Edit: In response to the comment from Nawaz below, the first method works because of the vagaries of two's complement signed integer arithmetic. Like I said, it takes the long way around. It is enabled, as others have pointed out because of some compiler optimization or another. You can see this in the code below for the test input previously provided:

int mul2(int a, int b)
{
    int rv = 0;
    while (b--) rv += a;
    return rv;
}

It in fact should work for any pair of integers but will take some time to run in some case (but I expect you weren't interested in efficiency in any event).

The second case does not work because your conditional b > 0 ? --b : ++b essentially converts b to abs(b). That is, you only add 7 times in your test case even though b = -7. If you wanted it to behave the way I think you wanted it to behave you would instead need to do something like:

int multiply(int a, int b)
{
  if ( !b )
     return 0;
  else if (b < 0)
     return -a + multiply(-a, -b-1);
  else
     return a + multiply(a, --b);
}

Edit 2: Try this instead:

short multiply(short a, short b)
{
  if ( !b )
     return 0;
  else
     return a + multiply(a, b ? --b : ++b );
}

and

short multiply(short a, short b)
{
  if ( !b )
     return 0;
  else
     return a + multiply(a, --b);
}

Both of these compile, run and return the same (correct) result with or without optimization. As others have pointed out, the cause of the execution time difference you are seeing can only be attributed to the way the compiler is optimizing your code. You will need to analyze the assembly code of the two methods to determine the root cause of the time discrepancies.

- andand

---

哦，天啊，是的！当出现问题时，加些日志！你不知道出了什么问题？再加些日志！还是不知道？再加更多日志！也许调试器也会有用的:D - deadalnix

@deadalnix：我明白了，我同意。尽管如此，这似乎比尝试从调试器中发布输出更容易和更快。 - andand

如果您希望了解优化的效果，请不要更改代码（在调试器中运行是可以的，只要您没有使用能够检测到调试器并关闭优化的高级JIT编译器）。 - Ben Voigt

@andand：这并没有回答问题。为什么第一个有效，而第二个无效，才是问题所在。 - Nawaz

@andand：还是没有回答我的问题。在第二个版本中，我没有使用 b > 0 ? --b : ++b。而是直接使用了 --b，结果并不起作用。 - Nawaz

Answer 4

实际上，这与--b无关，而与您的算法有关。

如果b < 0，你期望什么？你将无限循环并最终导致堆栈溢出。

这就是为什么你在首次调用multiply(12, 7)时得到了正确的结果，但当你调用multiply(12, -7)时，你的程序失败了。

- deadalnix

---

这就解释了为什么仅使用"--b"是不起作用的。但为什么'b ? --b : ++b'能够起作用呢？由于此时'b'始终为非零值，所以条件始终为真，从而总是导致"--b"。 - user395760

这个其他的情况也不应该起作用。你应该尝试看看编译器汇编的内容，我很确定它与你写的不同。你能否尝试一下没有二进制特殊属性（如7）的数字？ - deadalnix

Answer 5

由于二进制补码的工作方式，您的代码对于b的正值和负值都是“正确”的。只是对于负数b，任何递归版本都需要一个大的堆栈才能工作。因此，每当编译器发出非递归版本时，您就有了可用的代码。所以问题就在于：我的编译器内部使用什么规则来确定何时发出非递归代码。这取决于编译器的编写方式。

- jyoung

Answer 6

当b为负数时，Visual Studio中的两种形式的multiply都会导致堆栈溢出。

因此，答案是，两种形式都不正确。在gcc中发生的情况可能是由于某些怪异的（不是错误！）编译器优化了第一个示例中的尾递归，但没有优化第二个示例。

---

作为一个旁注，即使你将其更改为b>0？--b：++b，你仍然没有乘以b的符号（例如multiply（-1，-1）== -1 ）

- BlueRaja - Danny Pflughoeft

Answer 7

但令我惊讶的是，我本不打算写的代码也能够正常工作。显然，在g++的优化级别2中，编译器正确地看到了如果b为正数，则您的代码等同于a*b。它还显然看到，如果b为负数，则您的代码会引发未定义的行为。编译器通过在所有情况下推广为a*b来优化掉这种未定义的行为。以下是g++ -O2（i686-apple-darwin10-g++-4.2.1）的汇编程序：

.globl __Z8multiplyii
__Z8multiplyii:
LFB1477:
   pushq %rbp
LCFI0:
   movq  %rsp, %rbp
LCFI1:
   xorl  %eax, %eax
   testl %esi, %esi
   je L5
   movl  %esi, %eax
   imull %edi, %eax
L5:
   leave
   ret 

我不信任优化器。在我看来，编译器对于识别到未定义行为的响应应该是编译失败，而不是优化掉未定义行为。

编辑

我不会再添加另一个答案了，我会将另一个答案作为编辑添加。

问任何物理学家无穷级数1+2+3+...的值是多少，他们会告诉你它是-1/12。（例如，请参见http://math.ucr.edu/home/baez/qg-winter2004/zeta.pdf）。这种绕远路的方法通过类似的二进制补码算术技巧实现。一种不涉及负数绕远路的解决方案：

int multiply (int a, int b) {
   if (b == 0) {
      return 0;
   }
   else if (b < 0) {
      return -multiply (a, -b);
   }
   else {
      return a + multiply(a, b-1);
   }
}

即使在高度优化的情况下，我的编译器也不再足够聪明，无法将上述内容识别为乘法。将上述内容拆分为两个函数，编译器再次能够识别正在进行的是整数乘法。

int multiplyu(int a, unsigned int b) {
   return (b == 0) ? 0 : a + multiplyu(a, b-1);
}

int multiply(int a, int b) {
   return (b < 0) ? -multiplyu (a, -b) : multiplyu (a, b); 
}

- David Hammen

---

ideone.com 不使用任何优化，我认为。如果它使用了优化，那么它对两个程序都使用相同的优化。 - Nawaz

我已经在ideone上测试了按原样编写的代码，并尝试了各种优化级别。当使用没有优化或使用-O1编译代码时，我会收到segfault错误。当我使用-O2编译时，我得到了与ideone上呈现的结果相同的结果。我还查看了汇编语言。没有进行优化的编译器下multiply()是递归的，并且b是自动减量的。使用-O1编译multiply()仍然是递归的，但--b被替换为b-1。使用-O2编译将递归替换为整数乘法。 - David Hammen

很多时候，你会发现是-O0掩盖了UB，而更高的设置会暴露它。但这恰好是相反的情况。请注意，UB != 崩溃。整个重点在于行为未定义；因此，“优化UB”并没有真正意义上的意义。 - Oliver Charlesworth