微軟等數據結構與算法面試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;   
}