求 1+2+…+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
示例 1： 输入: n = 3 输出: 6
示例 2： 输入: n = 9 输出: 45
限制： 1 <= n <= 10000
递归 思路和算法
试想一下如果不加限制地使用递归的方法来实现这道题，相信大家都能很容易地给出下面的实现（以 C++ 为例）：
class Solution { public: int sumNums(int n) { return n == 0 ? 0 : n + sumNums(n - 1); } };通常实现递归的时候我们都会利用条件判断语句来决定递归的出口，但由于题目的限制我们不能使用条件判断语句，那么我们是否能使用别的办法来确定递归出口呢？答案就是逻辑运算符的短路性质。
以逻辑运算符 && 为例，对于 A && B 这个表达式，如果 A 表达式返回 False\textit{False}False ，那么 A && B 已经确定为 False\textit{False}False ，此时不会去执行表达式 B。同理，对于逻辑运算符 ||， 对于 A || B 这个表达式，如果 A 表达式返回 True\textit{True}True ，那么 A || B 已经确定为 True\textit{True}True ，此时不会去执行表达式 B。
利用这一特性，我们可以将判断是否为递归的出口看作 A && B 表达式中的 A 部分，递归的主体函数看作 B 部分。如果不是递归出口，则返回 True\textit{True}True，并继续执行表达式 B 的部分，否则递归结束。当然，你也可以用逻辑运算符 || 给出类似的实现，这里我们只提供结合逻辑运算符 && 的递归实现。
class Solution { public: int sumNums(int n) { n && (n += sumNums(n-1)); return n; } };方法二：快速乘 思路和算法
考虑 A 和 B 两数相乘的时候我们如何利用加法和位运算来模拟，其实就是将 B 二进制展开，如果 B 的二进制表示下第 iii 位为 1，那么这一位对最后结果的贡献就是 A∗(1<<i)A*(1<<i)A∗(1<<i) ，即 A<<iA<<iA<<i。我们遍历 B 二进制展开下的每一位，将所有贡献累加起来就是最后的答案，这个方法也被称作「俄罗斯农民乘法」，感兴趣的读者可以自行网上搜索相关资料。这个方法经常被用于两数相乘取模的场景，如果两数相乘已经超过数据范围，但取模后不会超过，我们就可以利用这个方法来拆位取模计算贡献，保证每次运算都在数据范围内。
下面给出这个算法的 C++ 实现：
int quickMulti(int A, int B) { int ans = 0; for ( ; B; B >>= 1) { if (B & 1) { ans += A; } A <<= 1; } return ans; }