牛客JZ65——不用四则运算作加法

题目描述

写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。
数据范围：两个数都满足 -10 ≤ _n _≤ 1000
进阶：空间复杂度 O(1)，时间复杂度 O(1)

链接：不用加减乘除做加法_牛客题霸_牛客网

示例

示例1
输入：1,2 返回值：3
示例2
输入：0,0 返回值：0

核心代码模式

int Add(int num1, int num2 )
{

}
1
2
3
4

思路分析和代码实现（C语言）

思路分析
首先看十进制是如何做的： 5+7=12，三步走

第一步：相加各位的值，不算进位，得到2。
第二步：计算进位值，得到10。如果这一步的进位值为0，那么第一步得到的值就是最终结果。
第三步：重复上述两步，只是相加的值变成上述两步的得到的结果2和10，得到12。

同样我们可以用三步走的方式计算二进制值相加： 5(101)，7(111)

第一步：相加各位的值，不算进位，得到010，二进制每位相加就相当于各位作异或操作，即101^111。
第二步：计算进位值，得到1010，相当于各位作与操作得到101，再向左移一位得到1010，(101&111)<<1。
第三步：重复上述两步， 各位相加 010^1010=1000，进位值为100=(010&1010)<<1。
再继续重复上述两步：1000^100 = 1100，进位值为0，跳出循环，1100为最终结果。
也就是一直到进位值为0为止。

实际上，在计算机中：
两个二进制的相加结果是用一个异或门实现的。
两个二进制的进位结果是用一个与门来实现的。

具体到代码上如何实现？用两个变量a和b分别存储非进位值和进位值，创建循环，只要b的值不为0就继续循环，每次循环中先用一个临时值tmp保存b的值，然后用b来装载进位值，也就是(a & b)<<1，用a来装载非进位值，即a^tmp（因为b先被改变了，得用b的副本）。等出了循环后返回a的值。

代码实现

int Add(int num1, int num2 ) 
{
    int a = num1;//放非进位值
    int b = num2;//放进位值
    
    while(b != 0)
    {
        int tmp = b;
        b = (a & b) << 1;
        a ^= tmp;
    }
    
    return a;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14