【LeetCode】剑指 Offer 65. 不用加减乘除做加法 p310 -- Java Version

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

1. 题目介绍（65. 不用加减乘除做加法）

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

【测试用例】：

【条件约束】：

2. 题解

2.1 位运算 – O(1) ⭐

时间复杂度O(1)，空间复杂度O(1)

【解题思路】：
该题解的思路就是将原本的加法运算，从底层思路出发，将原本的数字相加变为二进制的位数相加，将 原本的 a + b 转化为 n（无进位和） + c（进位），使用循环进行相加，直至进位为0为止，以 a = 1, b = 9 为例，可见下图：

class Solution {
    // s = a + b = n + c;
    public int add(int a, int b) {
        while (b != 0) {
            int c = (a & b) << 1;
            a ^= b;
            b = c;
        }
        return a;
    }
}

递归写法：

class Solution {
    // s = a + b = n + c;
    public int add(int a, int b) {
        return b == 0 ? a : add(a ^ b, (a & b) << 1);
    }
}

2.2 库函数（Integer.sum() & IntStream）

【解题思路】：
我们可以使用具有 sum() 方法的包装类实现数字的相加，但严格意义上 Integer.sum() 写法应该是不被允许的，因为它的底层其实就是两数相加：

而 IntStream 则不同，它的底层是一个 reduce：

IntStream写法：

class Solution {
    public int add(int a, int b) {
        IntStream intStream = IntStream.of(a,b);
        return intStream.sum();
    }
}

Integer.sum()写法：

class Solution {
    public int add(int a, int b) {
        return Integer.sum(a,b);
    }
}

3. 参考资料

[1] 面试题65. 不用加减乘除做加法（位运算，清晰图解）-- Krahets