剑指offer-65：不用加减乘除做加法

60 阅读 0 评论 40 点赞

我是靠谱客的博主俭朴戒指，最近开发中收集的这篇文章主要介绍剑指offer-65：不用加减乘除做加法，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

这道题题目可以描述为：写一个函数，求两个整数之和，要求在函数体内不得使用加减乘除四则运算符号。

解题思路可以分为以下两个步骤：

（1）以5和17为例，5的二进制是101,17的二进制是10001。把计算可以分为三步：第一步各位相加但不计进位，得到的结果是10100；第二步记下进位，这个例子中只在最后一位相加时产生一个进位，结果是二进制的10。第三步把前两步的结果相加，得到的结果是10110，转换成十进制正好是22。

（2）接下来试着把二进制的加法用位运算来代替。第一步不考虑进位对每一位相加。0加0、1加1的结果都是0,0加1、1加0的结果都是1。可以注意到，这和异或的结果是一样的。接着考虑第二步进位，对0加0、0加1、1加0而言，都不会产生进位，只有1加1时，会向前产生一个进位。由此可以考虑为两个数先做位与运算，然后再向左移动一位。第三步把前两个步骤的结果相加。第三步相加的结果依然是重复前面两步，直到不产生进位为止。

代码如下：

#include<stdio.h>
int Add(int num1, int num2)
{
int sum, carry;
do
{
sum = num1^num2;
carry = (num1&num2) << 1;
num1 = sum;
num2 = carry;
} while (num2 != 0);
return num1;
}