题目：求1+2+..+n
求 1+2+…+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/qiu-12n-lcof
分析
这道题如果你有什么大胆的想法，直接做就是了（手动滑稽）。
先来分析一下，首先拿到这道题，第一反应就是我们熟悉的数学公式 (n+1)n/2。但是这里需要用到乘法和除法，不满足题干。那么接下来分析一下我们还有什么运算符可以用：
加减法，赋值，位运算，逻辑运算。
看到位运算是不是眼前一亮。运算可以取代加减乘除，本质上加减乘除也是用位运算来实现的。所以，怎么用位运算实现乘法和除法？
除法是二的指数就很简单了，直接移位就行了。非二的倍数就比较复杂，这里先不讨论。
乘法的话，看乘数化为二进制的每一位是不是1.如果是1则被乘数向左移动该位的位置数（第一位默认是0）。例如：2*3: = 010 * 011：
- 3的第一位是1，那么结果加上010向左移动0位，即010
- 3的第二位是1，那么结果加上010向左移动1位，即010+100=110
- 3的第三位是0，结果保持不变，最终是110 即6.
这样就可以得到答案了。
但是我们给出的n的大小不确定，又不能用循环判断，那怎么去不断累加呢？
注意限制条件：1<=n<=10000 。n不会超过·10000，也就是n的二进制位数不会超过14，所以弄14层代替循环即可。没错就是这么暴力。
这道不同编程语言的逻辑运算可参与的数据类型不同。c/c++中可以用整数来进行逻辑运算，但是java等面向对象的语言是不可以的。要注意这点。
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
| public int sumNums(int n) {
int ans = 0, A = n, B = n + 1;
boolean flag;
flag = ((B & 1) > 0) && (ans += A) > 0;
A <<= 1;
B >>= 1;
flag = ((B & 1) > 0) && (ans += A) > 0;
A <<= 1;
B >>= 1;
flag = ((B & 1) > 0) && (ans += A) > 0;
A <<= 1;
B >>= 1;
flag = ((B & 1) > 0) && (ans += A) > 0;
A <<= 1;
B >>= 1;
flag = ((B & 1) > 0) && (ans += A) > 0;
A <<= 1;
B >>= 1;
flag = ((B & 1) > 0) && (ans += A) > 0;
A <<= 1;
B >>= 1;
flag = ((B & 1) > 0) && (ans += A) > 0;
A <<= 1;
B >>= 1;
flag = ((B & 1) > 0) && (ans += A) > 0;
A <<= 1;
B >>= 1;
flag = ((B & 1) > 0) && (ans += A) > 0;
A <<= 1;
B >>= 1;
flag = ((B & 1) > 0) && (ans += A) > 0;
A <<= 1;
B >>= 1;
flag = ((B & 1) > 0) && (ans += A) > 0;
A <<= 1;
B >>= 1;
flag = ((B & 1) > 0) && (ans += A) > 0;
A <<= 1;
B >>= 1;
flag = ((B & 1) > 0) && (ans += A) > 0;
A <<= 1;
B >>= 1;
flag = ((B & 1) > 0) && (ans += A) > 0;
A <<= 1;
B >>= 1;
return ans >> 1;
}
|
复杂度分析
- 时间复杂度：只需要遍历n的二进制位数
时间复杂度：O(logn)
- 空间复杂度：只需要额外的常量空间
空间复杂度：O(1)
