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的值。
- 样例输入：
-
35
- 样例输出：
-
615
题意分析： 给定正整数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 #include4 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 }