剑指offer面试题：不用加减乘除做加法

四种解法，只有想不到，没有做不到！！

题目描述

求1+2+3+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

四种解法，只有想不到，没有做不到！！

解法一：短路求值

class Solution {
public:
    int Sum_Solution(int n) {
        int ans = n;
        ans && (ans += Sum_Solution(n - 1));
        return ans;
    }
};

解法二：利用异常

用异常退出递归。

//用异常退出递归
public class Solution {
    public int Sum_Solution(int n) {
        return sum(n);
    }
    int sum(int n){
        try{
            int i = 1%n;
            return n+sum(n-1);
        }
        catch(Exception e){
            return 0;
        }
    }
}

解法三：乘法->sizeof

用公式是不可以的，公式里有乘法！！实现乘法可以用sizeof多维数组，两行代码就可以：

class Solution {
public:
    int Sum_Solution(int n) {
        bool a[n][n+1];
        return sizeof(a)>>1;
    }
};

解法四：乘法->快速模乘

马客(Mark)：
我就猜到大家都是用 && 的短路原则的，这样复杂是O(n)的。
我来一个复杂度32的，可以说O(logM)吧，M是数值大小，对于int也可以说是O(1)吧虽然常数有点大。

原理就是，类似快速幂，俗称快速模乘。

a * b可以这样算：

res = 0
while(a){
    if(a & 1) res += b;
    a >>= 1;
    b <<= 1; 
}

原理是把a拆成2的幂的和，a = 2^e0 + 2^e1 + 2^e2....
那么 a * b = (2^e0 + 2^e1 + 2^e2+...) * b = b * 2^e0 + b * 2^e1 + b * 2^e2 + ... = (b << e0) + (b << e1) + ....

也就是看成了二进制的相乘。可以写成如下代码【然而用了while】

class Solution {
public:
    int Sum_Solution(int n) {
        // res = (n+1)xn/2
        int a = n, b = n + 1, ans = 0;
        while(a) {
            if(a & 1) {
                ans += b;
            }
            a >>= 1;
            b <<= 1;
        }
        return ans >> 1;
    }
};

由于不能使用while语句，所以符合题意的代码如下：

//奇数返回0xffffffff，否则0
#define f(x) ((((x) & 1) << 31) >> 31)
class Solution {
public:
    int Sum_Solution(int n) {
        int a = n, b = n + 1, s = 0;
        //复制32次。。
        s += b & f(a); a >>= 1; b <<= 1;
        s += b & f(a); a >>= 1; b <<= 1;
        s += b & f(a); a >>= 1; b <<= 1;
        s += b & f(a); a >>= 1; b <<= 1;
        s += b & f(a); a >>= 1; b <<= 1;
        s += b & f(a); a >>= 1; b <<= 1;
        s += b & f(a); a >>= 1; b <<= 1;
        s += b & f(a); a >>= 1; b <<= 1;
         
        s += b & f(a); a >>= 1; b <<= 1;
        s += b & f(a); a >>= 1; b <<= 1;
        s += b & f(a); a >>= 1; b <<= 1;
        s += b & f(a); a >>= 1; b <<= 1;
        s += b & f(a); a >>= 1; b <<= 1;
        s += b & f(a); a >>= 1; b <<= 1;
        s += b & f(a); a >>= 1; b <<= 1;
        s += b & f(a); a >>= 1; b <<= 1;
         
        s += b & f(a); a >>= 1; b <<= 1;
        s += b & f(a); a >>= 1; b <<= 1;
        s += b & f(a); a >>= 1; b <<= 1;
        s += b & f(a); a >>= 1; b <<= 1;
        s += b & f(a); a >>= 1; b <<= 1;
        s += b & f(a); a >>= 1; b <<= 1;
        s += b & f(a); a >>= 1; b <<= 1;
        s += b & f(a); a >>= 1; b <<= 1;
         
        s += b & f(a); a >>= 1; b <<= 1;
        s += b & f(a); a >>= 1; b <<= 1;
        s += b & f(a); a >>= 1; b <<= 1;
        s += b & f(a); a >>= 1; b <<= 1;
        s += b & f(a); a >>= 1; b <<= 1;
        s += b & f(a); a >>= 1; b <<= 1;
        s += b & f(a); a >>= 1; b <<= 1;
        s += b & f(a); a >>= 1; b <<= 1;
        return s >> 1;
    }
};