不用加减乘除做加法
不用加减乘除做加法
http://www.nowcoder.com/questionTerminal/59ac416b4b944300b617d4f7f111b215
描述
这是一篇针对初学者的题解
知识点:位运算
难度:二星
题解
题目描述:不使用加减乘除来实现两数加法、
方法:位运算
知识补充:
按位与&,按位或|, 按位异或^
![图片说明](https://uploadfiles.nowcoder.com/images/20200505/284295_1588686434571_209BD4459BD002D912E85E54433CA4C4 "图片标题")补码
计算机中存整数n是用补码存的。
- 如果n为正数,则原码=反码=补码
- 如果n为负数,则补码=反码+1
本题是考察对位运算的运用,使用位运算来实现两数的加法。
设两数字的二进制形式 a,b ,其求和 s = a + b ,a(i) 代表 a 的二进制第 i 位,则分为以下四种情况:
![图片说明](https://uploadfiles.nowcoder.com/images/20200505/284295_1588687181635_F1F0A0DAE581028E686FC568F55694CE "图片标题")
观察发现,无进位和运算就是按位异或结果,进位就是与运算结果但是需要左移一位,因为进位影响下一位的运算。
所以s = a + b,其实就是无进位和+进位的结果。
算法步骤:
- 计算a和b的无进位和,和进位
- 如果进位不为0,则说明a+b的结果等于无进位和+进位,此时,把无进位和作为a,进位作为b,继续计算
- 如果进位等于0, 说明此时a+b的结果就等于无进位和,返回无进位和即可。
如图:
![图片说明](https://uploadfiles.nowcoder.com/images/20200505/284295_1588688021116_933571186EC12CADAFC6064813BE06D4 "图片标题")
Q:你可能有疑问,如果是一个数为负数或者两个数都为负数怎么办?
A:上述补码的介绍,补码就是解决减法的问题,计算机把减法看做加法来运算。
所以代码如下:
class Solution { public: int Add(int num1, int num2) { while (num2 != 0) { // 负数左移会在低位补1,所以转化为无符号整数 int c = ((unsigned int)(num1 & num2)) << 1; num1 ^= num2; num2 = c; } return num1; } };
时间复杂度:O(1)
空间复杂度:O(1)