不用加减乘除做加法——位运算的实践

一、题目

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

二、解题思路

本题考察对位运算的灵活使用，即使用位运算实现加法。
设两数字的二进制形式 a，b，其求和 s=a+b，a(i) 代表 a 的二进制第 i 位，则分为以下四种情况：

观察发现，无进位和 与 异或运算 规律相同，进位 和 与运算 规律相同（并需左移一位）。因此，无进位和 n 与进位 c 的计算公式如下：

即可将 s=a+b 转化为：

s=a+b⇒s=n+c

循环求 n 和 c ，直至进位 c=0；此时 s=n，返回 n 即可。

三、代码

非递归

class Solution {
public:
    int add(int a, int b) {
          while(b != 0) { // 当进位为 0 时跳出
            int c = (unsigned int)(a & b) << 1;  // c = 进位
            a ^= b; // a = 非进位和
            b = c; // b = 进位
        }
        return a;

    }
};

递归

class Solution {
    public:
     int add(int a, int b) {
        if (b == 0) {
            return a;
        }
        
        // 转换成非进位和 + 进位
        return add(a ^ b, (unsigned int)(a & b) << 1); // C++中负数不支持左移位，因为结果是不定的
    }
};

参考：

https://leetcode-cn.com/problems/bu-yong-jia-jian-cheng-chu-zuo-jia-fa-lcof/solution/mian-shi-ti-65-bu-yong-jia-jian-cheng-chu-zuo-ji-7/