求 1+2+...+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
示例 1：
输入: n = 3
输出: 6
示例 2：
输入: n = 9
输出: 45
限制： 1 <= n <= 10000
class Solution {
public:
int quick_c(int a, int b) {
int ans = 0;
while (b)
{
if (b & 1) ans = (ans+a);
a = (a+a);
b >>= 1;
}
return ans;
}
int sumNums(int n) {
return quick_c(n+1,n)>>1;
}
};
解题思路：
本题在简单问题上做了许多限制，需要使用排除法一步步导向答案。
1+2+...+(n-1)+n1+2+...+(n−1)+n 的计算方法主要有三种：平均计算、迭代、递归。
方法一： 平均计算
问题： 此计算必须使用 乘除法 ，因此本方法不可取，直接排除。
javapython
public int sumNums(int n) {
return (1 + n) * n / 2;
}
方法二： 迭代
问题： 循环必须使用 whilewhile 或 forfor ，因此本方法不可取，直接排除。
javapython
public int sumNums(int n) {
int res = 0;
for(int i = 1; i <= n; i++)
res += i;
return res;
}
方法三： 递归
问题： 终止条件需要使用 ifif ，因此本方法不可取。
思考： 除了 ifif 和 switchswitch 等判断语句外，是否有其他方法可用来终止递归？
javapython
public int sumNums(int n) {
if(n == 1) return 1;
n += sumNums(n - 1);
return n;
}
逻辑运算符的短路效应：
常见的逻辑运算符有三种，即 “与 \&\&&& ”，“或 ||∣∣ ”，“非 !! ” ；而其有重要的短路效应，如下所示：
if(A && B)
if(A || B)
本题需要实现 “当 n = 1n=1 时终止递归” 的需求，可通过短路效应实现。
n > 1 && sumNums(n - 1)
复杂度分析：
时间复杂度 O(n)O(n) ： 计算 n + (n-1) + ... + 2 + 1n+(n−1)+...+2+1 需要开启 nn 个递归函数。
空间复杂度 O(n)O(n) ： 递归深度达到 nn ，系统使用 O(n)O(n) 大小的额外空间。
代码：
Java 中，为构成语句，需加一个辅助布尔量 xx ，否则会报错；
Java 中，开启递归函数需改写为 sumNums(n - 1) > 0 ，此整体作为一个布尔量输出，否则会报错；
初始化变量 resres 记录结果。（ Java 可使用第二栏的简洁写法，不用借助变量 resres ）。
javajavapython
class Solution {
int res = 0;
public int sumNums(int n) {
boolean x = n > 1 && sumNums(n - 1) > 0;
res += n;
return res;
}
}
方法二：快速乘
思路和算法
考虑 A 和 B 两数相乘的时候我们如何利用加法和位运算来模拟，其实就是将 B 二进制展开，如果 B 的二进制表示下第 ii 位为 1，那么这一位对最后结果的贡献就是 A*(1<<i)A∗(1<<i) ，即 A<<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;
}
回到本题，由等差数列求和公式我们可以知道 1 + 2 + \cdots + n1+2+⋯+n 等价于 \frac{n(n+1)}{2}
2
n(n+1)
，对于除以 22 我们可以用右移操作符来模拟，那么等式变成了 n(n+1)>>1n(n+1)>>1，剩下不符合题目要求的部分即为 n(n+1)n(n+1)，根据上文提及的快速乘，我们可以将两个数相乘用加法和位运算来模拟，但是可以看到上面的 C++ 实现里我们还是需要循环语句，有没有办法去掉这个循环语句呢？答案是有的，那就是自己手动展开，因为题目数据范围 nn 为 [1,10000][1,10000]，所以 nn 二进制展开最多不会超过 1414 位，我们手动展开 1414 层代替循环即可，至此满足了题目的要求，具体实现可以参考下面给出的代码。
C++JavaTypeScriptGolang
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;
}
};
复杂度分析
时间复杂度：O(\log n)O(logn)。快速乘需要的时间复杂度为 O(\log n)O(logn)。
空间复杂度：O(1)O(1)。只需要常数空间存放若干变量
