面试题65. 不用加减乘除做加法

不用加减乘除做加法

题目描述

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

示例：

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

提示：
a, b 均可能是负数或 0
结果不会溢出 32 位整数

转载来源：力扣（LeetCode）

题目分析

这题我用了两种做法，分别复习 加法器 和 位运算，下面先看 加法器 版本：

• 加法器

1. 初始化，结果为0，当前位为32bit int的最低位，也就是0x 1，进位为0
2. a、b分别和当前位作 与 运算，结果代表a（b）的最后一位是否为1
3. 下面分 2^3 中情况
   3.1 a_now ！= 0，b_now ！= 0，c == 1，这相当于1+1+1，进位为1，当前位结果为1，
   3.2 a_now ！= 0，b_now ！= 0，c == 0，这相当于1+1+0，进位为1，当前位结果为0，
   3.3 a_now ！= 0，b_now == 0，c == 1，这相当于1+0+1，进位为1，当前位结果为0，
   3.4 a_now ！= 0，b_now == 0，c == 0，这相当于1+0+0，进位为0，当前位结果为1，
   3.5 a_now == 0，b_now ！= 0，c == 1，这相当于0+1+1，进位为1，当前位结果为0，
   3.6 a_now == 0，b_now ！= 0，c == 0，这相当于0+1+0，进位为0，当前位结果为1，
   3.7 a_now == 0，b_now == 0，c == 1，这相当于0+0+1，进位为0，当前位结果为1，
   3.8 a_now == 0，b_now == 0，c == 0，这相当于0+0+0，进位为0，当前位结果为0，
4. 每计算一次，当前位左移一位，回到2
5. int型有32位，只需要执行32遍就好

为了方便理解，这里我的 if-else 没有做简化和优化

    public int add(int a, int b) {
        int result = 0;
        int c = 0; 
        int now = 1;
        while(a != 0 && now != 0){
            int lowA = a & now;
            int lowB = b & now;
            if(lowA != 0){
                if(lowB != 0){
                    if(c == 1){
                        c = 1;
                        result |= now;
                    }else{
                        c = 1;
                    }
                }else{
                    if(c == 1){
                        c = 1;
                    }else{
                        c = 0;
                        result |= now;
                    }
                }
            }else{
                if(lowB != 0){
                    if(c == 1){
                        c = 1; 
                    }else{
                        c = 0;
                        result |= now;
                    }
                }else{
                    if(c == 1){
                        c = 0;
                        result |= now;
                    } 
                }
            }
            now <<= 1;
        }
        while(b != 0 && now != 0){
            int lowB = b & now;
            if(lowB != 0){
                if(c == 1){
                    c = 1;
                }else{
                    result |= now;
                }
            }else{
                if(c == 1){
                    c = 0;
                    result |= now;
                }
            }
            now <<= 1;
        }
        return result;
    }

• 位运算

计算a + b时，进位可以用 （a & b）<< 1，来表示，当前位可以用（a ^ b）来表示，举个例子：
 5 + 5 = 10
 二进制形式：0101 + 0101 = 1010
 （a ^ b） = 0000
 （a & b）<< 1 = 0101 << 1 = 1010
 （a ^ b）+ （a & b）<< 1 = 1010
 可以表示为 当前位 加 进位

好像好有道理，但好像也没道理，因为还是需要计算（a ^ b）+ （a & b），里面有 + 法

那就用继续回到第一步，继续用这个方法来算这个 + 法呀，递归循环都好:

    public int add(int a, int b) {
        while (b != 0) {
            int c = (a ^ b);  
            b = ((a & b) << 1);  
            a = c;
        } 
        return a;
    }