题目的主要信息：

• 计算$1+2+3+\mathrm{.}\mathrm{.}\mathrm{.}+n1+2+3+...+n$
• 不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）

方法一：与（&&）的短路递归

具体做法：

不能循环，我们可以递归实现连加，只要从n加到1即可。但是我们需要判断递归停止的条件，即到0时停止递归，不能用if、switch、？：等操作，我们可以采用与运算的短路操作： 在函数中，如果与运算成立，则继续，否则终止函数直接返回false。

class Solution {
public:
    int res = 0;
    int Sum_Solution(int n) {
        n && (n += Sum_Solution(n - 1)); //要判断n是否为整数
        return n;
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，一共递归$nn$次
• 空间复杂度：$O(n)O(n)$，递归栈深度为$nn$

方法二：计算内存

具体做法：

我们有如下计算：

$1+2+3+\mathrm{.}\mathrm{.}\mathrm{.}+n=(n+1)\ast n\mathrm{/}2=sizeof(a[n][n+1])\mathrm{/}2=sizeof(a)>>11+2+3+...+n=(n+1)*n/2=sizeof(a[n][n+1])/2\; =\; sizeof(a)>>1$ 其中数组a我们可以设置为bool型，只占一个空间，因此二维数组所占空间的一半就是我们要求的值。

class Solution {
public:
    int res = 0;
    int Sum_Solution(int n) {
        bool a[n][n + 1]; //创建一个n*(n+1)的数组
        return sizeof(a) >> 1; //返回这个数组空间的一半
    }
};

复杂度分析：

• 时间复杂度：$O(1)O(1)$，直接计算，常数时间
• 空间复杂度：$O(n^2)O(n^2)$，辅助数组a的空间大小

方法三：快速乘法

具体做法：

由方法3我们知道了我们需要计算$n(n+1)>>1n(n+1)>>1$即可。乘法不允许被使用，我们可以用快速乘法的加法来代替，快速乘法如下：

就比如$a\ast b=a\ast (b_1+b_2+b_3+\mathrm{.}\mathrm{.}\mathrm{.})a\mathrm{\ast }b=a\mathrm{\ast }(b_1+b_2+b_3+\mathrm{.}\mathrm{.}\mathrm{.})a*b=a*(b\_1+b\_2+b\_3+...)a\ast b=a\ast (b\_1+b\_2+b\_3+...)$，其中$b_{i}b\_i$是数字$bb$的二进制各位，假设$a=5a=5$，$b=110101b=110101$，我们有$a\ast b=a\ast (100000\ast 1+10000\ast 1+1000\ast 0+100\ast 1+10\ast 0+1\ast 1)a*b=a*(100000*1+10000*1+1000*0+100*1+10*0+1*1)$，如下表所示可以换成加法运算:

换成加法运算以后的代码为：

int fast(int x, int y){ //快速乘法
        int res = 0;
        while(y){
            if(y & 1){
                res += x; 
            }
            y = y >> 1;
            x = x << 1;
        }
        return res;
    }

这个算法中就全是加法和移位算法，但是还有循环和判断，判断我们可以用与运算解决，循环其实就是数字的位数，我们这里数字不会超过14位，因此我们将循环拆开直接写14次。

class Solution {
public:
    int res = 0;
    int Sum_Solution(int n) {
        int res = 0;
        int A = n, B = n + 1;
        //14次快速乘法
        (B & 1) && (res += A);
        A <<= 1;
        B >>= 1;
        (B & 1) && (res += A);
        A <<= 1;
        B >>= 1;
        (B & 1) && (res += A);
        A <<= 1;
        B >>= 1;
        (B & 1) && (res += A);
        A <<= 1;
        B >>= 1;
        (B & 1) && (res += A);
        A <<= 1;
        B >>= 1;
        (B & 1) && (res += A);
        A <<= 1;
        B >>= 1;
        (B & 1) && (res += A);
        A <<= 1;
        B >>= 1;
        (B & 1) && (res += A);
        A <<= 1;
        B >>= 1;
        (B & 1) && (res += A);
        A <<= 1;
        B >>= 1;
        (B & 1) && (res += A);
        A <<= 1;
        B >>= 1;
        (B & 1) && (res += A);
        A <<= 1;
        B >>= 1;
        (B & 1) && (res += A);
        A <<= 1;
        B >>= 1;
        (B & 1) && (res += A);
        A <<= 1;
        B >>= 1;
        (B & 1) && (res += A);
        A <<= 1;
        B >>= 1;
        return res >> 1; //除2
    }
};

复杂度分析：

• 时间复杂度：$O(1)O(1)$，常数时间
• 空间复杂度：$O(1)O(1)$，常数空间