剑指offer-求1+2+……+n

本文为剑指offer系列第二篇。
个人感觉属于奇淫巧技，但是是真的很巧妙，有利于打破思维定势。

题目描述

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

解题思路

思路1: 其实可以调用库函数。
思路2: 可以使用 && 和 || 的短路机制。
思路3: 使用sizeof运算符和右移操作。

解题代码

朴素思想代码

先写出求和公式，后面的几种方法再想办法绕开题目限制。

class Solution {
public:
    int Sum_Solution(int n) {
        return (1+n)*n/2;
    }
};

思路1代码

class Solution {
public:
    int Sum_Solution(int n) {
        return fma(fma(n,n+1,0),0.5,0);
    }
};

fma(x,y,z)函数作用是返回x*y+z. 我们让z为0,就变成了单纯的乘法。

思路2代码

class Solution {
public:
    int Sum_Solution(int n) {
        int sum  = n;
        bool b = (n>0) && (sum += Sum_Solution(n-1))>0;
        return sum;
    }
};

思路3代码

这个方法利用数组所占的字节数来计算。由于n是运行时参数，变长数组依赖GNU/Clang扩展，严格的标准C++模式下不能编译；而且需要O(n^2)的栈空间，n较大时可能栈溢出。如果要使用标准C++，可以选择上面的短路递归。

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

因为sizeof运算符可以用来计算对象空间大小，每个char是1个字节，所以对于大小为n*(n+1)的二维数组而言，空间就是n*(n+1). 结果右移一位等同于除以2.
由此我们可以推广到其他的数据类型上。比如在sizeof(int)等于4的环境中，数组占用4n(n+1)个字节，要得到求和结果就需要右移3位。

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

以上，本题结束！