剑指offer四十八之不用加减乘除做加法

一、题目

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

二、思路

1、　采用位运算的方法，分三步：

　　（1）、两个数异或：相当于每一位相加，而不考虑进位

　　（2）、两个数相与，并左移一位：相当于求得进位

　　（3）、重复步骤1和2，两个数相与的结果为0，和即为两个数异或的结果

2、例子演示：

3+11 = ？

13 的二进制 1 1 0 1 -----a 13

11 的二进制 1 0 1 1 -----b 11

(a&b) <<1 -> 1 0 0 1 0 -----d 18

a^b -> 0 1 1 0 -----e 6

(d&e) <<1 -> 0 0 1 0 0 -----f 4

d^e -> 1 0 1 0 0 -----g 20

(f&g) <<1 -> 0 1 0 0 0 ------h 8

f^g -> 1 0 0 0 0 ------i 16

(h&i) <<1 -> 0 0 0 0 0 ------h 0 ---- --------退出循环

h^i -> 1 1 0 0 0 ------i 24

在第一步中，采用异或

第二步中，采用按位与，左移一位

三、代码

public class Solution {
    public int Add(int num1,int num2) {
        while( num2!=0 ){ //当进位等于0的时候，返回异或的结果，即是要求的和
            int sum = num1 ^ num2; //两个数异或：相当于每一位相加，而不考虑进位
            int carray = (num1 & num2) << 1;//两个数相与：并左移一位：相当于求得进位
            num1 = sum;
            num2 = carray;
        }
        return num1;
    }
}

View Code

---------------------------------------------

参考链接：

https://www.nowcoder.com/questionTerminal/59ac416b4b944300b617d4f7f111b215