每日一练（34）：不用加减乘除做加法

---

title: 每日一练（34）：不用加减乘除做加法

categories:[剑指offer]

tags:[每日一练]

date: 2022/03/09

---

每日一练（34）：不用加减乘除做加法

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

示例:

输入: a = 1, b = 1

输出: 2

提示：

a, b 均可能是负数或 0

结果不会溢出 32 位整数

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/bu-yong-jia-jian-cheng-chu-zuo-jia-fa-lcof

方法一：位运算

算法流程：

a ^ b 计算出2个加数二进制下每一位的本位

a & b 计算出2个加数二进制下每一位的进位

(a & b) << 1 进位做进位逻辑，也就是 * 2

int add(int a, int b) {
    while (b != 0) {
        int carry = a & b ;  // 计算 进位
        a ^= b;             // 计算 本位
        b = (unsigned)c << 1;   
    }
    return a;
}

方法二：递归

加法=进位+非进位部分

利用异或位运算来表示不进位的情况 00=0 11=0 10=1 01=1

利用与运算和左移运算来表示进位的情况 11=10

在循环中也要进行左移操作

int add(int a, int b) {
    // 后续用a表示非进位和，b表示进位，当进位为0，则表示计算结束
    return b ? add(a ^ b, (unsigned)(a & b) << 1) : a;
}