不用加减乘除做加法

剑指Offer题解(Java实现)



1 题目描述


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


2 思路


通过位运算模拟加法操作,主要考虑两种情况,一种是相加不产生进位,直接异或即为结果;另一种是相加产生进位,则将异或的结果加上进位。

  1. 不考虑进位的情况, num1 + num2 其实就是 num1 ^ num2(异或);
  2. 如果相加过程中产生进位,即 num1&num2 不等于 0 ,则将 num1&num2 左移一位再与前面异或的结果相加。

例子:5 + 7

5 的二进制表示:101

7 的二进制表示:111

  1. 5 和 7 异或:010;
  2. 5 & 7:不等于 0 ,左移一位,1010;
  3. 将 010 和 1010 分别作为加数,重复 1、2 步。


3 代码实现


public class Solution {
    public int Add(int num1,int num2) {
        int sum = 0;
        int carry = 0;
        
        while(num2!=0){
            sum = num1 ^ num2;
            carry = (num1&num2)<<1;
            num1 = sum;
            num2 = carry;
        }
        
        return num1;
    }
}


 
comments powered by Disqus