[C++知识库]剑指 Offer 64. 求1+2+…+n（C++）

描述：求 1+2+…+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）

限制：1 <= n <= 10000

归纳在LeetCode上看到的3个解法(C++语法)。

解法1：递归，短路语句

int fun(int n){
	n && (n += fun(n-1));
	return n;
}

解法2：计算内存

int fun(int n){
	bool a[n][n+1];
	return sizeof(a)>>1;
}

解法3：俄罗斯农民乘法，由于1 <= n <= 10000的限制，故变量n的二进制展开最多不会超过 14 位，故手动执行14次即可

int fun(int n){
	int ans=0, a=n, b=n+1;
	
	(b&1) && (ans+=a);
	a <<= 1;
	b >>= 1;
	
	(b&1) && (ans+=a);
	a <<= 1;
	b >>= 1;
		
	(b&1) && (ans+=a);
	a <<= 1;
	b >>= 1;
		
	(b&1) && (ans+=a);
	a <<= 1;
	b >>= 1;
		
	(b&1) && (ans+=a);
	a <<= 1;
	b >>= 1;
		
	(b&1) && (ans+=a);
	a <<= 1;
	b >>= 1;
		
	(b&1) && (ans+=a);
	a <<= 1;
	b >>= 1;
		
	(b&1) && (ans+=a);
	a <<= 1;
	b >>= 1;
		
	(b&1) && (ans+=a);
	a <<= 1;
	b >>= 1;
		
	(b&1) && (ans+=a);
	a <<= 1;
	b >>= 1;
		
	(b&1) && (ans+=a);
	a <<= 1;
	b >>= 1;
		
	(b&1) && (ans+=a);
	a <<= 1;
	b >>= 1;
		
	(b&1) && (ans+=a);
	a <<= 1;
	b >>= 1;
		
	(b&1) && (ans+=a);
	a <<= 1;
	b >>= 1;
	
	return ans>>1;
}

以上就是我目前看到的3种比较好的相关解法。