【牛客 - 剑指offer】JZ65 不用加减乘除做加法 位运算、递归、非递归实现 Java实现

---

剑指offer题解汇总 Java实现

https://blog.csdn.net/guliguliguliguli/article/details/126089434

本题链接

知识分类篇 - 位运算 - JZ65 不用加减乘除做加法

题目

思路 & 代码

方案一 递归

把所有的数字都转换成二进制来看待

如果不考虑进位的话，那么 a + b 的结果就是 a ^ b 的结果

异或：相同为0，相异为1
比如：13 + 11
1101 13
1011 11
在不考虑进位的情况下，两个数进行异或运算，结果是：
0110

什么时候进位？在相同位上都是1的情况下需要进位，根据这一特点，可以使用 & 运算符，找出需要进位的那些位

与运算：相同为1，相异为0
比如13 、11
1101 13
1011 11
二者经过与运算以后的结果是
1001

说明在13 + 11 的运算过程中，需要进位的是第一位和最后一位，把这个结果向左移一位

01001
左移一位
10010 对应的十进制数是：$2^4+2^1=18$，正好是11+13的结果

向左移一位以后，与异或运算的结果相加，得到想要的结果

00110 异或结果
10010 与运算结果左移一位
二者相加
11000 对应的十进制数是：$2^4+2^3=16+8=24$

但是，在题目中说明了不能使用加、减、乘、除运算

可以发现，在求解完两个数的异或，以及与运算结果向左移一位，这两个步骤以后，有需要执行加法运算，所以可以再次调用Add()方法，即递归操作

import java.util.*;

public class Solution {
    public int Add(int num1, int num2) {
        if (num1 == 0 || num2 == 0) {
            return num1 ^ num2;
        }
        return Add(num1 ^ num2, (num1 & num2) << 1);
    }
}
1
2
3
4
5
6
7
8
9
10

具体运算流程

方案二 非递归

非递归的方法，就是使用循环来代替递归调用

import java.util.*;

public class Solution {
    public int Add(int num1, int num2) {

        while (num1 != 0 && num2 != 0) {
            int temp = num1 ^ num2;
            num2 = (num1 & num2) << 1;
            num1 = temp;
        }
        return num1 ^ num2;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13