算法 1.2.2 两整数之和(不使用“+”)【leetcode

题目描述

两整数之和
不使用运算符 + 和 - ，计算两整数 a 、b 之和。

示例 1:
输入: a = 1, b = 2
输出: 3

示例 2:
输入: a = -2, b = 3
输出: 1

数据结构

• bit

算法思维

• 位运算，递归

解题要点

• 利用二进制位运算实现 相加 和 进位 的功能

---

解题思路

一. Comprehend 理解题意

需要使用其他方式实现 “+” 的功能
可以使用位操作实现：
两个二进制数在某位上的数字相加的结果，与该位上两数字的 异或运算 结果一致，因此可以使用异或运算得到某个 bit 上两数字的相加结果
而进位的值相当于本位两数字做 与运算 的结果向左做1次 移位运算

算法原理

• 异或运算 = 本位相加结果
• 与运算 + 移位 = 本位进位
• 递归

流程示意

注意：进位结果需要与相加结果再次“相加”，直到没有任何一位出现进位为止 -- 递归调用

二. Choose 选择数据结构与算法

数据结构：bit
算法思维：位运算（先不使用递归）
时间复杂度：O(?)
空间复杂度：O(1) -- 只占用一个整数的内存空间

三. Code 编码实现基本解法

class Solution{
 public int getSum(int a, int b) {

        // 提示：视作二进制数，本位结果用异或求得，进位用与运算和移位运算求得

        int and = (a & b) << 1;
        int xor = a ^ b;
        int tmp = 0;

        while(and != 0){
            tmp = xor ^ and;
            and = (xor & and) << 1;
            xor = tmp;
        }

        return xor;
    }
}

执行耗时：0 ms，击败了100.00% 的Java用户
内存消耗：35 MB，击败了84.85% 的Java用户

四. Consider 思考更优解

改变算法思维：位运算 + 递归
时间复杂度：O(?)
空间复杂度：O(1)

五. Code 编码实现最优解

class Solution{
   public int getSum(int a, int b) {
        if (b != 0){
            int and = (a & b) << 1;
            int xor = a ^ b;
            return getSum(xor,and);
        }
        return a;
    }
}

执行耗时：0 ms，击败了100.00% 的Java用户
内存消耗：35 MB，击败了85.71% 的Java用户

六. Change 变形与延伸

=== 待续 ===