题解 | #求1+2+3+...+n#

JZ47 求1+2+3+...+n

题意分析：

求连加到n的和。

示例输入：5
返回：1+2+3+4+5=15

题解一（高斯公式）：

。

int Sum_Solution(int n) {//
    return n * (n + 1) / 2;
}

值得注意的是，该解法不满足题意要求

题解二(循环)：

循环叠加即可。

intSum_Solution(int n) {
    int ret = 0;
    for (int i = 1; i <= n; i++)
        ret += i;
    return ret;
}

这种解法也不满足题意。

题解三（修改循环）

上面循环，我们可以用递归代替，写成如下形式。

int Sum_Solution(int n){
    if(n = 0){
        return n;
    }
    else{
        return n+Sum_Solution(n-1);
    }
}

但是这里有条件控制，无妨，我们使用位运算代替即可。

int Sum_Solution(int n) {
    n && (n += Sum_Solution(n - 1));
    return n;
}

题解四（修改高斯公式）：

高斯公式，/2我们可以使用>>1表示。至于我们似乎无法使用位运算表示。

但是可以使用奇怪的方法：比如可以写成 。8和1都可以用二进制表示。我们可以将其中一个数以二进制展开，然后取位运算。我们可以写成这样代码。

int Sum_Solution(int n) {
    int ret = 0;
    int a = n;
    int b = n + 1;
    while (a > 0) {
        (a & 1) && (ret += b);
        a = a >> 1;
        b = b << 1;
    }
    ret = ret >> 1;
    return ret;
}

里面的while循环，我们可以手动去掉，因为最多只循环32次。我们将循环体部分手写32遍（还是不建议的），哈哈。