如何使这个递归函数运行得更快

Question

int add2_recurse(int a, int b) { // recursive
// Rule: Can't use the *, /, +, =, *=, /=, +=, -= operators.
// Can use: ++ and/or --
// No loops allowed; no static local or global variables.

// What I have so far
while(b--) {
    a++;
return a; }

---

int main() {
show_test(4, "add2", recursive);
cout << add2_recurse(4,5); cout<<" ";  // correct:   9
cout<<add2_recurse(-5, 15); cout<<" ";  // correct:  10
cout<<add2_recurse(20, -9); cout<<" ";  // correct:  11
cout<<add2_recurse(-7, -5); cout<<" ";  // correct: -12
cout<<endl;

---

当我运行它时，显示"9 10 11 -12"的正确输出，只有 11 和 -12 显示得更慢。关于如何让它运行得更快的任何想法？

Answer 1

首先，你的解决方案是错误的，原因有两个。你不使用递归，你使用的是循环。

至于为什么它在最后两种情况下运行得这么慢：每当b为负数时，b一直递减到最小可能的整数，然后它绕到最大可能的整数，最后递减直到它是 0。假设一个 32 位整数，您将有大约 40 亿次循环迭代。

您需要区分b的负值和正值，然后根据需要递减或递增a。

Answer 2

你不需要任何递归，加法在按位运算方面是相当简单的实现的：

#include <limits.h> /* CHAR_BIT for pedantic correctness */
int add(int a_, int b_)
{
    /*
    Signed types tend to have UB. Prevent this by using unsigned.
    This might only work with twos-complement systems, sorry - patches welcome.
    */
    const unsigned a = (unsigned)a_;
    const unsigned b = (unsigned)b_;
    unsigned s = 0, c = 0;
    int i;
    /* constant-sized loop, can be trivially unrolled if you know how many bits are in an int (e.g. 16 or 32) */
    for (i = 0; i < sizeof(int) * CHAR_BIT; ++i)
    {
        s |= ((a ^ b ^ c) & (1 << i));
        c = ((a & b) | (a & c) | (b & c)) & (1 << i);
        c <<= 1;
    }
    return (signed)s;
}

当心上述代码中的错误;我只是证明了它是正确的，没有尝试过。