微软等数据结构与算法面试100题 第十二题
第十二题
题目：求1+2+…+n，
要求不能使用乘除法、for、while、if、else、switch、case 等关键字以及条件判断语句（A?B:C）。
说明：本文对两种方法进行汇总，参考http://blog.csdn.net/daxiamit/article/details/7611088 中第12题目中指出美国阿财的解答 和 July原先给出的解答。
因此这里在写文章的标题写的是原创，而不是转载，特此声明。
美国阿财给出的解答：
ANSWER:
1+..+n=n*(n+1)/2=(n^2+n)/2
it is easy to get x/2, so the problem is to get n^2
though no if/else is allowed, we can easilly go around using short-pass.
using macro to make it fancier:
#define T(X, Y, i) (Y & (1<<i)) && X+=(Y<<i)
int foo(int n){
int r=n;
T(r, n, 0); T(r, n,1); T(r, n, 2); … T(r, n, 31);
return r >> 1;
}
我表示很疑惑的是 为什么不能直接计算n^2和n/2呢？
代码：
#include <iostream> #include <iomanip> #include <limits> using namespace std; class nplus{ public: static int cnt; static int sum; static unsigned long plus; nplus(){++cnt; sum += cnt;plus *= cnt;} ~nplus(){} }; int nplus::cnt = 0; int nplus::sum = 0; unsigned long nplus::plus = 1; int main() { nplus np[10]; cout << "sum: " << nplus::sum << " plus: " << nplus::plus << endl; return 0; }