面试题64. 求1+2+…+n

难度：中等

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

示例 1：

输入: n = 3
输出: 6
示例 2：

输入: n = 9
输出: 45

思路1：运用逻辑与的短路效应。对于a && b，如果a为false，直接跳过对b的操作。通过这个效应，可对递归的结束条件进行判定。

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

思路2：递推公式为 n(n+1)​/2。乘法可通过移位得到，即快速乘（又叫俄罗斯农民乘法）

考虑 A 和 B 两数相乘的时候我们如何利用加法和位运算来模拟，其实就是将 B 二进制展开，如果 B 的二进制表示下第 i 位为 1，那么这一位对最后结果的贡献就是 A*(1<<i) ，即A<<i。我们遍历 B 二进制展开下的每一位，将所有贡献累加起来就是最后的答案。

leetcode官方题解代码为，因为二进制位不会超过14位，则手动展开了14位计算。

class Solution {
public:int sumNums(int n) {int ans = 0, A = n, B = n + 1;(B & 1) && (ans += A);A <<= 1;B >>= 1;(B & 1) && (ans += A);A <<= 1;B >>= 1;(B & 1) && (ans += A);A <<= 1;B >>= 1;(B & 1) && (ans += A);A <<= 1;B >>= 1;(B & 1) && (ans += A);A <<= 1;B >>= 1;(B & 1) && (ans += A);A <<= 1;B >>= 1;(B & 1) && (ans += A);A <<= 1;B >>= 1;(B & 1) && (ans += A);A <<= 1;B >>= 1;(B & 1) && (ans += A);A <<= 1;B >>= 1;(B & 1) && (ans += A);A <<= 1;B >>= 1;(B & 1) && (ans += A);A <<= 1;B >>= 1;(B & 1) && (ans += A);A <<= 1;B >>= 1;(B & 1) && (ans += A);A <<= 1;B >>= 1;(B & 1) && (ans += A);A <<= 1;B >>= 1;return ans >> 1;}
};

这里我将快速乘与逻辑与短路相结合得到如下代码：

class Solution {
public:int ans=0;int sumNums(int n) {mul(n,n+1);return ans>>1;}int mul(int a,int b){b & 1 && (ans+=a);b && (mul(a<<1,b>>1));return ans;}
};