剑指Offer - 九度1506 - 求1+2+3+...+n


文章转载自:http://www.pythonheidong.com/blog/article/2880/

剑指Offer - 九度1506 - 求1+2+3+...+n
2013-11-29 19:22
题目描述:

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

输入:

输入可能包含多个测试样例。
对于每个测试案例,输入为一个整数n(1<= n<=100000)。

输出:

对应每个测试案例,
输出1+2+3+…+n的值。

样例输入:
3
5
样例输出:
6
15
题意分析:
  给定正整数n,范围不超过100000,求1 + ... + n的和,那么也就是求n * (n + 1) / 2的值,但是:不准用乘除法和循环之类的写法。注意:可以用加法
  很明显,不准用循环的话,要么重复写N遍,要么递归。不准我用乘除,就用位操作模拟乘除。虽然毕业后就再没接触过Verilog和加法器乘法器,但学到的设计思想决不能忘了,否则学费不白交了吗?
  注意下面俩式子:
    x^a * x^b = x^(a + b)
    (a[n] * x^n + a[n - 1] * x^(n - 1) + ... + a[0]) * (b[m] * x^m + b[m - 1] * x^(m - 1) + ... + b[0]) = 两两相乘一大堆
  既然计算机中二进制操作这么方便,我们可以将一个数按二进制展开:14 = 2^3 + 2^2 + 2^1,于是两个数相称就成了两个x=2的多项式相乘了。
  接下来,2^a * 2^b = 2^(a + b) = 1 << (a + b)
  有了上面的思路,我们考虑整数a * b,如果a和b都是32位整数,那么a的所有二进制位和b的所有二进制位乘积的和。接下来就参考Verilog中的常规写法了:
  第一层“循环”,fun1():
    fun1(0);
    fun1(1);
    ...
    fun1(31);
  
  第二层循环,在fun1中再调用多个fun2():
    fun2(0);
    fun2(1);
    ...
    fun2(31);
  Verilog里不建议用for循环是有原因的,毕竟电路设计和写软件不一样,具体原因可自行百度“Verilog for”。但这种写法还真可以避免使用循环,满足面试题的要求。
  最后还有两点:
    1. 题目中n的范围不超过十万,因此二进制位数不超过17位,循环写17个其实就够了。
    2. 结果范围明显可以超出int范围,用long long int吧。
 1 // 653472    zhuli19901106    1506    Accepted    点击此处查看所有case的执行结果    1020KB    1606B    50MS
 2 // 201311190134
 3 #include <cstdio>
 4 using namespace std;
 5 
 6 void add2(long long int &x, long long int &y, int i, int j, long long int &res)
 7 {
 8     res += (((!!(x & (1 << i))) & (!!(y & (1 << j)))) << (i + j));
 9 }
10 
11 void add1(long long int &x, long long int &y, int i, long long int &res)
12 {
13     add2(x, y, i, 0, res);
14     add2(x, y, i, 1, res);
15     add2(x, y, i, 2, res);
16     add2(x, y, i, 3, res);
17     add2(x, y, i, 4, res);
18     add2(x, y, i, 5, res);
19     add2(x, y, i, 6, res);
20     add2(x, y, i, 7, res);
21     add2(x, y, i, 8, res);
22     add2(x, y, i, 9, res);
23     add2(x, y, i, 10, res);
24     add2(x, y, i, 11, res);
25     add2(x, y, i, 12, res);
26     add2(x, y, i, 13, res);
27     add2(x, y, i, 14, res);
28     add2(x, y, i, 15, res);
29     add2(x, y, i, 16, res);
30     add2(x, y, i, 17, res);
31     add2(x, y, i, 18, res);
32     add2(x, y, i, 19, res);
33 }
34 
35 int main()
36 {
37     long long int n;
38     long long int res;
39     long long int x, y;
40     
41     while(scanf("%lld", &n) == 1){
42         res = 0;
43         x = n;
44         y = n + 1;
45         add1(x, y, 0, res);
46         add1(x, y, 1, res);
47         add1(x, y, 2, res);
48         add1(x, y, 3, res);
49         add1(x, y, 4, res);
50         add1(x, y, 5, res);
51         add1(x, y, 6, res);
52         add1(x, y, 7, res);
53         add1(x, y, 8, res);
54         add1(x, y, 9, res);
55         add1(x, y, 10, res);
56         add1(x, y, 11, res);
57         add1(x, y, 12, res);
58         add1(x, y, 13, res);
59         add1(x, y, 14, res);
60         add1(x, y, 15, res);
61         add1(x, y, 16, res);
62         add1(x, y, 17, res);
63         add1(x, y, 18, res);
64         add1(x, y, 19, res);
65         res >>= 1;
66         printf("%lld\n", res);
67     }
68 
69     return 0;
70 }

 

文章转载自:http://www.pythonheidong.com/blog/article/2880/


作者:雄霸天下-无人能挡,发布于:2019/08/15
原文:https://www.cnblogs.com/xiongbatianxiaskjdskjdksjdskdtuti/p/11356376.html