写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。
数据范围：两个数都满足 
进阶：空间复杂度)
，时间复杂度
进阶：空间复杂度
[编程题]不用加减乘除做加法
咩咩jiang
//step1:按位与是查看两个数哪些二进制位都为1，这些都是进位位，结果需左移一位，表示进位后的结果
//step2:异或是查看两个数哪些二进制位只有一个为1，这些是非进位位，可以直接加、减，结果表示非进位位进行加操作后的结果
//step3:n1&n2是查看有没有进位位了，如果有，需要重复step1、step2；如果没有，保留n1、n2上二进制为1的部分，用或将之合为一个数，即为最后结果
class Solution {
public:
int Add(int num1, int num2)
{
int n1,n2;
n1=(num1&num2)<<1;
n2=num1^num2;
while(n1&n2)
{
num1=n1;num2=n2;
n1=(num1&num2)<<1;
n2=num1^num2;
}
return n1|n2;
}
};
编辑于 2015-08-18 23:38:52
回复(19)
public class Solution {
public int Add(int num1,int num2) {
while (num2!=0) {
int temp = num1^num2;
num2 = (num1&num2)<<1;
num1 = temp;
}
return num1;
}
} 首先看十进制是如何做的： 5+7=12，三步走 第一步：相加各位的值，不算进位，得到2。 第二步：计算进位值，得到10. 如果这一步的进位值为0，那么第一步得到的值就是最终结果。 第三步：重复上述两步，只是相加的值变成上述两步的得到的结果2和10，得到12。 同样我们可以用三步走的方式计算二进制值相加： 5-101，7-111 第一步：相加各位的值，不算进位，得到010，二进制每位相加就相当于各位做异或操作，101^111。 第二步：计算进位值，得到1010，相当于各位做与操作得到101，再向左移一位得到1010，(101&111)<<1。 第三步重复上述两步， 各位相加 010^1010=1000，进位值为100=(010&1010)<<1。 继续重复上述两步：1000^100 = 1100，进位值为0，跳出循环，1100为最终结果。 部门开始招聘实习生，感兴趣的同学可以看看，可以内推 https://www.nowcoder.com/jobs/detail/307599?jobId=307599
编辑于 2024-02-06 18:14:52
回复(97)
class Solution {
public:
int Add(int num1, int num2)
{
char* a = reinterpret_cast<char*>(num1);
return reinterpret_cast<long>(&(a[num2]));
}
};
发表于 2016-10-04 15:26:22
回复(9)
class Solution {
public:
int Add(int num1, int num2)
{
//相加各位 + 计算进位
//十进制思想
//5+7 各位相加：2 进位：10
//2+10 12 0
//12+0
//二进制计算过程
//5+7 各位相加：101^111=010 进位：101&111=101 (<<1=1010)
//2+10 各位相加：010^1010=1000 进位：010&1010=010 <<1=0100
//8+4 1000^0100=1100 1000&0100=0
//12+0
if (num2 == 0) return num1;
return Add(num1^num2, (num1&num2)<<1 );
}
};
编辑于 2017-04-19 13:47:43
回复(0)
class Solution {
public:
int Add(int num1, int num2)
{
int result=0;
__asm__(
"add %1,%2\n\t" //%1表示num2 %2表示num1,这个表示num2的值加到num1上
"mov %2,%0\n\t" //%0表示目的寄存器,把num1复制到result上
:"=r"(result) //%0,占用符号
:"r"(num2),"r"(num1) //这一行是将C代码中的数据输入到汇编的代码中
);
return result;
}
};
发表于 2017-01-25 00:24:58
回复(0)
import java.math.*;
public class Solution {
public int Add(int num1,int num2) {
BigInteger sum1=new BigInteger(String.valueOf(num1));
BigInteger sum2=new BigInteger(String.valueOf(num2));
BigInteger res=sum1.add(sum2);
String a=res.toString();
int solution=Integer.valueOf(a);
return solution;
}
}
发表于 2016-06-12 12:31:43
回复(6)
利用位运算代替加法。步骤如下：
【1】不考虑进位。0+0,1+1结果都是0；0+1,1+0结果都是1，也就是异或操作
【2】考虑进位。0+0,0+1,1+0不会产生进位，1+1会向前产生一个进位。因此可以将两个数先做位与运算，再左移一位（0&0,0&1,1&0结果都是0，左移结果不变；1&1结果是1，左移一位10表示向前进一位）
python 中最后运算结果是按补码进行存储，正数补码是本身，负数补码是该数绝对值的所有位取反再加1。举例来说，如果最后结果是-15，然而不做处理的话xorNum=4294967281（111....110001，15原码或补码为0...01111），该数为-15的补码但是被python认为是一个Long型的长整数。将上述结果与0xFFFFFFFF取异或，可以得到上述数的绝对值15，再取反，得到最后结果。这种操作看似做了个无用操作，但是告诉python解释器这个结果不是长整型，而是被作为负数解释输出。
【1】不考虑进位。0+0,1+1结果都是0；0+1,1+0结果都是1，也就是异或操作
【2】考虑进位。0+0,0+1,1+0不会产生进位，1+1会向前产生一个进位。因此可以将两个数先做位与运算，再左移一位（0&0,0&1,1&0结果都是0，左移结果不变；1&1结果是1，左移一位10表示向前进一位）
【3】上述两个步骤相加，但是不允许相加操作，所以重复上述过程，直到没有进位。
class Solution: def Add(self, num1, num2): # write code here # 异或、与（与计算考虑进位）之和 xorNum = num1 ^ num2 # 不考虑进位 andNum = (num1 & num2)<<1 # 考虑进位 while andNum!=0: # 若果没有进位的话直接输出结果 tmp1 = xorNum ^ andNum tmp2 = (xorNum & andNum)<<1 tmp1 = tmp1 & 0xFFFFFFFF # 为了避免负数过大，取前32位 xorNum = tmp1 andNum = tmp2 return xorNum if xorNum<=0x7FFFFFFF else ~(xorNum^0xFFFFFFFF)
python 中最后运算结果是按补码进行存储，正数补码是本身，负数补码是该数绝对值的所有位取反再加1。举例来说，如果最后结果是-15，然而不做处理的话xorNum=4294967281（111....110001，15原码或补码为0...01111），该数为-15的补码但是被python认为是一个Long型的长整数。将上述结果与0xFFFFFFFF取异或，可以得到上述数的绝对值15，再取反，得到最后结果。这种操作看似做了个无用操作，但是告诉python解释器这个结果不是长整型，而是被作为负数解释输出。
编辑于 2020-03-16 11:33:44
回复(1)
Java实现，已通过。运行时间：19ms，占用内存：9328k。不能用四则运算，就只能考虑位运算。
两个数相加是这样的：先不考虑进位，将两个数进行无进位相加：1+1=0, 0+0=0, 1+0=1,这是异或运算:int UnsignedSum=num1^ num2; 接下来需要求出进位位，1+1=0时会向前产生一个进位位，而其他情况:0+0 0+1没有进位位，可以想到相与运算，只有1&1=1,其他相与结果都是0，这个1左移1位就能得到所有进位位: signedSum=(num1 & num2 )<<1 (这里一定要带括号，因为<<优先于& )将这个 signedSum继续与UnsignedSum相加，就会重复上述：先是无进位相加，再求进位 ......所以在方法里需要将UnsignedSum赋给num1， 将signedSum赋给num2,直到不产生进位了，signedSum=0为止，代码如下：
public class Solution {
public int Add(int num1,int num2) {
//直到不再产生进位
while (num2!=0)
{//无进位求和
int UnsignedSum=num1^num2;
//求出进位
int signedSum=(num1&num2)<<1;
num1=UnsignedSum;
num2=signedSum;}
//直到进位num2为0，说明不再产生进位，num1就是最终结果
return num1;
}
} 也可以写成递归形式：运行时间：16ms,占用内存：9404k
//写成递归形式
//第一个参数放无进位相加结果，第二个参数放进位位
//方法：求两个参数的和
public int Add(int num1,int num2) {
if(num2==0) return num1;
return Add(num1^num2,(num1&num2)<<1);
} 2020 二刷
public class Solution {
public int Add(int num1,int num2) {
if(num2==0) return num1;
return Add(num1^num2,(num1&num2)<<1);
}
} public class Solution {
public int Add(int num1,int num2) {
while (num2!=0) {
int UnDigit = num1 ^ num2;
int Digit = (num1 & num2) << 1;
num1 = UnDigit;
num2 = Digit;
}
return num1;
}
} 2021 三刷： public class Solution {
public int Add(int num1,int num2) {
while(num2!=0){
int unsinged=num1 ^ num2;
int signed=(num1 & num2)<<1;
num1=unsinged;
num2=signed;}
return num1;
}
}
编辑于 2021-02-10 20:36:33
回复(0)
public class Solution { public int Add(int num1,int num2) { if (num2==0) return num1; return Add(num1^num2, (num1&num2)<<1); } }
- 异或运算（^）： 如果a、b两个值不相同，则异或结果为1。如果a、b两个值相同，异或结果为0
- 与运算（&）：两位同时为“1”，结果才为“1”，否则为0
1、化简
1. 先看一个例子：
看一下 3 + 4 的加法运算
3 的二进制表示： 011
4 的二进制表示： 100
3^4 (3按位异或4)的结果是： 111 => 7
上面的到的结果是就是 3 + 4 的实际结果
再看一个例子：
12 的二级制表示: 01100
19 的二进制表示: 10011
12^19 的结果是： 11111 => 31
再看一个例子：
13 的二进制表示：01101
19 的二进制表示：10011
13^19 的结果是： 11110 => 20
通过上面的三个例子不难发现: 当二进制数的每一位加法中不发生进位时，按位异或的结果就是最终的加法结果，那么我需要做的就是将所有的加法操作最终都简化成没有进位的加法操作，最终的结果就是两个数按位异或的结果。
2、怎么处理有进位的加法？
拆分
将两个数的加法拆分为 进位加法和不进位加法
看一个例子：
编号：1 2 3 4 5
------------------------
1 0 0 1 1 => 19
+ 1 1 0 1 0 => 26
--------------------------
先求只有不进位的两个位相加的值，编号为2、3、5这三位的加法不发生进位操作，需要进位的相加位数直接按照结果为0处理，得到的结果为
编号：1 2 3 4 5
------------------------
1 0 0 1 1
+ 1 1 0 1 0
------------------------
不进位： 0 1 0 0 1
进位两个位相加的值，编号为1、4这三位的加***发生进位操作，不需要进位的直接按照结果0处理，得到的结果为：
编号：1 2 3 4 5
------------------------
1 0 0 1 1
+ 1 1 0 1 0
------------------------
不进位： 0 1 0 0 1
进 位： 1 0 0 1 0 0
再将两个结果按位异或：
不进位：0 0 1 0 0 1
进 位：1 0 0 1 0 0
------------------------
1 0 1 1 0 1 => 45
由此可见可以将一个二进制加法拆分为有进位的位数相加结果 和 无进位的位数相加的结果最终按位异或
3、递归
再看一个例子
编号：1 2 3 4 5
------------------------
1 0 1 1 1 => 23
+ 1 1 0 1 1 => 27
------------------------
不进位： 0 1 1 0 0 => 12
进 位： 1 0 0 1 1 0 => 38
通过一次相加得到的结果不能完全实现化简操作，所以需要递归地进行化简操作
编号：1 2 3 4 5
------------------------
1 0 1 1 1 => 23
+ 1 1 0 1 1 => 27
------------------------
不进位： 0 0 1 1 0 0 => 12
进 位：1 0 0 1 1 0 => 38
------------------------
不进位：1 0 1 0 1 0 => 42
进 位：0 0 1 0 0 0 => 8
------------------------
不进位：1 0 0 0 1 0 => 34
进 位：0 1 0 0 0 0 => 16
------------------------
不进位：1 1 0 0 1 0 => 50
进 位：0 0 0 0 0 0 => 0
以上实例通过递归的方式可以得到最终的结果
二、位运算实现
通过以上几个实例我们明白了如何通过二进制的几个步骤来实现任意整数的加法操作，现在我们需要把这件事情用位运算进行表示。
位运算表示不进位加法：
不进位加法其实就是一个异或操作
位运算表示进位加法：
进位加法其实就是一个与操作的结果左移一位
编辑于 2019-07-01 20:40:33
回复(0)
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
