剑指offer面试题65(java版):不用加减乘除做加法

welcome to my blog

剑指offer面试题65(java版):不用加减乘除做加法

题目描述

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

第四次做; 核心: 1) 要讲清楚这道题, 就是要分析sum的构成, sum = 无进位相加的结果 + 只考虑进位的结果 2) 当a+b不产生进位时, 可以使用a^b代替a+b

class Solution {
public int add(int a, int b) {
//异或是无进位相加
//当a+b的结果不产生进位时, 可以使用a^b替换a+b
int res = a^b;
int carry = a&b;
while(carry != 0){
int tmp = res ^ (carry<<1);
carry = res & (carry<<1);
res = tmp;
}
return res;
}
}

//求和结果有两部分: 无进位相加的结果 + 只考虑进位的结果
class Solution {
public int add(int a, int b) {
//无进位相加的结果
int res = a^b;
//进位的结果
int carry=a&b;
//循环的目的:直到其中一个加数为0(也就是没有进位的情况)
while(carry!=0){
a = res;
b = carry<<1;
//update
res = a ^ b;
carry = a & b;
}
return res;
}
}

思路

• 步骤1: 不进位相加
• 步骤2: 计算进位值
• 步骤3: 只要进位值不为0, 就重复步骤1和步骤2

第三次做,算是明白了什么是无进位相加, 其实就是两个加数对应二进制的某一位一个是1另一个是0, 这样相加不会产生进位, 所以两个加数的异或结果就是无进位相加; 有无进位相加就有进位相加, 也就是两个加数对应二进制的某一位都是1, 所以两个加数相与的结果就是相加后会产生进位的位, 进位的结果就是两个加数相与的结果再左移一位; 还要清楚代码循环中的进位为什么一定会变成0? 因为进位值不会增加新的1,只会保持1的数量不变或者减少1, 最重要的是进位值会不断向左移位, 所以进位值中的1总会都消失的,也就是进位值等于0; 再好好理解代码注释中的核心

/*
核心
a + b = sum
a ^ b 是无进位相加
a % b 是相加后会产生进位的位
(a % b) << 1是对产生进位的位进位的结果
所以 sum = a ^ b + ((a & b) << 1)
由于不能使用加法,所以如果sum = a + b这个等式中b=0, 那么a就是最终的结果了
如何让b等于0是关键
*/
public class Solution {
public int Add(int num1,int num2) {
int temp;
while(num2!=0){
temp = num1 ^ num2;//仅考虑不会产生进位的位相加的结果
num2 = (num1 & num2) << 1; //仅考虑会产生进位的位相加的结果; 为什么这么循环后, num2一定为0; 因为当前num2中的1会比上一次循环时左移一位
num1 = temp;
}
return num1;
}
}

第二次做, 重点:异或是无进位相加; (num1&num2)<<1的结果是sum减去无进位相加后的结果, 也就是num1^num2和(num1&num2)<<1相加等于sum; num1^num2 + (num1&num2)<<1 = sum. 具体见注释

public class Solution {
public int Add(int num1,int num2) {
int temp;
/*
循环时:
进位值不为0
循环的目的,num1和num2可以用无进位相加得到结果
5+7=12为例
循环把5+7分解成
5+7= 2+10 = 8+4 = 12+0 = 12
*/
while(num2 != 0){
temp = num1 ^ num2; //无进位相加
/*计算sum-无进位相加后的结果
比如
第一次无进位相加结果是2,那么num2=12 - 2 = 10
第二次无进位相加结果是8,那么num2=12 - 8 = 4
第三次无进位相加结果是12,那么num2=0
挑出循环,没有第四次
*/
num2 = (num1 & num2) << 1;
num1 = temp;
}
}
}

// 进位值为0之前, 要在下一轮循环中把不进位相加的结果和进位值进行不进位相加
public class Solution {
public int Add(int num1,int num2) {
int s;
while(num2!=0){ // 步骤3: 重复步骤1和步骤2
s = num1 ^ num2; // 步骤1:不进位相加
num2 = (num1 & num2) << 1;// 步骤2:计算进位值, 进位值为0,则步骤1是结果, 进位值不为0则需要进入下一轮循环重复
num1 = s; // 保留步骤1的结果
}
return num1;
}
}

未通过的答案, 混乱的逻辑, 作为教训

public class Solution {
public int Add(int num1,int num2) {
int s, f;
while(num2!=0){
s = num1 ^ num2; // 步骤1:不进位求和
f = (num1 & num2) << 1; // 步骤2:将需要进位的位置1
num1 = s ^ f;
// 步骤3: 步骤1+步骤2
num2 = s & f; //更新num2, 检查是否仍有进位
}
return num1;
}
}

不使用新的变量, 交换两个变量的值

方法1

a = a + b;
b = a - b;
a = a - b;

方法2

a = a ^ b;
b = a ^ b;
a = a ^ b;

最后

以上就是无语衬衫为你收集整理的剑指offer面试题65(java版):不用加减乘除做加法的全部内容，希望文章能够帮你解决剑指offer面试题65(java版):不用加减乘除做加法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。