题目链接

牛客网

题目描述

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

解题思路

a ^ b 表示没有考虑进位的情况下两数的和，(a & b) << 1 就是进位。

递归会终止的原因是 (a & b) << 1 最右边会多一个 0，那么继续递归，进位最右边的 0 会慢慢增多，最后进位会变为 0，递归终止。

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

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

问题

Q ： 若数字 a 和 b 中有负数，则变成了减法，如何处理？
A ： 在计算机系统中，数值一律用 补码 来表示和存储。补码的优势： 加法、减法可以统一处理（CPU只有加法器）。因此，以上方法 同时适用于正数和负数的加法 。

class Solution {
public:
    int add(int a, int b) {
        while(b!=0){ // 当进位为 0 时跳出
            int c = (unsigned int)(a&b)<<1; // c = 进位   负数左移会在低位补1，所以转化为无符号整数
            a = a^b; // a = 非进位和   n
            b = c; // b = 进位   c
        }
        return a;
    }
};
// 递归写法
class Solution {
    public int add(int a, int b) {
        if (b == 0) {
            return a;
        }
        // 转换成非进位和 + 进位
        return add(a^b, (a&b)<<1);
    }
}

• 时间复杂度 O(1)： 最差情况下（例如 a = 0x7fffffff , b = 1 时），需循环 32 次，使用 O(1) 时间；每轮中的常数次位操作使用 O(1) 时间。
• 空间复杂度 O(1)： 使用常数大小的额外空间。