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

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

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

• 题目
• 解题
• • 方法一：位运算

题目

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

示例:

输入: a = 1, b = 1
输出: 2

解题 方法一：位运算

参考链接

由于这种解法对于负数也是可以的，负数是通过补码实现的，正数通过原码。

补充：
如果为8位整型,
+5的二进制 原码 0000 0101 (正数实现)
-5的二进制 原码 1000 0101
-5的二进制 反码 1111 1010 (除符号位，对原码取反)
-5的二进制 补码 1111 1011 (负数实现）

可以验证 ~5+1 结果就是-5
+0表示 0000 0000
-1 表示 1111 1111

比如-2+3
-2 的二进制 1111 1110
3 的二进制 0000 0011
通过相加，得到的二进制为 0000 0001 也就是1。

迭代

class Solution {
public:
    int add(int a, int b) {
        //后续每次循环将  非进位a与进位b，继续相加，直到无进位为止。
        while(b!=0){
            int c=static_cast(a&b)<<1; //进位
            a^=b; //非进位
            b=c;
        }
        return a;
    }
};

递归

class Solution {
public:
    int add(int a, int b) {
        if (b == 0) {      // b=0也就是进位c=0，因此结果为非进位和n,也就是a
            return a;
        }
        return add(a ^ b, static_cast(a & b) << 1);     // n=a^b，c= (a & b) << 1; 将a=n，b=c 继续递归 （注: leetcode不支持负值左移，需要强制转换(a&b)为无符号数）
    }
};