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

题目描述

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

输入输出

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

基本思路

直接看解析

  • 无进位和：n=a⊕b(异或)
  • 进位和：c=(a&b)左移一位
  • 循环到b进位和不为0为止 result = n + c

补充：异或定义 如果a、b两个值不相同，则异或结果为1 如果a、b两个值相同，异或结果为0

java实现

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int add(int a, int b) {//a=1 b=2
        while(b != 0){
            int c = (a & b) << 1;//c 进位和 c=0
            a = a^b;//或写成a^=b 即无进位和 b=3
            b = c;
        }
        return a;
    }
}