不用加减乘除做加法

题目：写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。

图1  十进制和二进制做对照

代码实现：

一、 迭代（循环）

int Add(int num1, int num2) {
	int res = num1 ^ num2;
	int cheat = num1 & num2;	//判断是否产生进位
	/*
	**如果不产生进位，异或运算之后的值
	**  与做加法的值相同
	*/
	while (cheat) {
		cheat <<= 1;
		int temp = res;
		res ^= cheat;
		cheat &= temp;
	}
	return res;
}

代码缺点：参数列表中的形参num1和num2只使用了一次，但是其生存期是整段函数，故而还有改进的空间。 

图2  原始迭代版本运行结果

充分利用现有资源做出改进 

int Add(int num1, int num2) {
	/*
	**附加含义：将num1作为返回值；num2用于检查是否产生进位
	*/
	while (num2) {
		int res = num1 ^ num2;	//用于保存异或结果
		num2 = (num1 & num2) << 1;	//检查是否产生进位
		num1 = res;
	}
	return num1;
}

图3  改进迭代版本运行结果

二、 递归

int Add(int num1, int num2){
    /*
     *附加功能：函数参数列表第一个参数的意义是保存异或结果；
       第二个参数的意义是检查有无进位
    */
    return num2 ? Add(num1^num2, (num1&num2)<<1) : num1;
}

图4 递归版本运行结果

三、 总结

迭代（循环）和递归都只是手段。迭代（循环）是面向过程的，递归是面向对象的，也不知道这个比喻是否恰当。在我看来，迭代需要一步步给出具体实现细节；递归只要给出递归的形式和终止条件即可。我相信，只有思路很清晰，循环写的很熟练的前提下，才能很好地使用递归。