微软等数据结构与算法面试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呢？

代码：
[cpp]
#include<iostream>
using namespace std;

#define Ti(X, Y, i) (Y & (1<<i)) && (X=X+(Y<<i))
int foo(int n){
    int r=n;
    Ti(r, n, 0);
    Ti(r, n, 1);
    Ti(r, n, 2);
    Ti(r, n, 3);
    Ti(r, n, 4);
    Ti(r, n, 5);
    Ti(r, n, 6);
    Ti(r, n, 7);
    Ti(r, n, 8);
    Ti(r, n, 9);
    Ti(r, n, 10);
    Ti(r, n, 11);
    Ti(r, n, 12);
    Ti(r, n, 13);
    Ti(r, n, 14);
    Ti(r, n, 15);
    Ti(r, n, 16);
    Ti(r, n, 17);
    Ti(r, n, 18);
    Ti(r, n, 19);
    Ti(r, n, 20);
    Ti(r, n, 21);
    Ti(r, n, 22);
    Ti(r, n, 23);
    Ti(r, n, 24);
    Ti(r, n, 25);
    Ti(r, n, 26);
    Ti(r, n, 27);
    Ti(r, n, 28);
    Ti(r, n, 29);
    Ti(r, n, 30);
    Ti(r, n, 31);

    return r >> 1;
}

int main()
{
     cout<<endl;
    cout<<foo(9)<<endl;
    return 0;
}

july给出的分析：主要是如何通过一个static变量存储中间的结果，这个是问题的核心。
代码参考 http://blog.csdn.net/zshtang/article/details/6611399
代码：
[cpp]
#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;
}

补充：软件开发 , C++ ,

微软等数据结构与算法面试100题 第十二题

微软等数据结构与算法面试100题第十二题