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

in with 0 comment

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

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

示例:

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

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/bu-yong-jia-jian-cheng-chu-zuo-jia-fa-lcof 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路

  1. 转为二进制进行位运算,可将数字拆分为当前位和进位,当前位的加法相当于 异或(加数相同为 0,不同为 1),进位的运算相当于 与(加数都为 1,才为 1),进位时需要将数字左移一位,直到数字为 0。

代码

解法一

class Solution {
    public int add(int a, int b) {
        while (b != 0) {
            int c  = (a & b) << 1;
            a ^= b;
            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);
    }
}