本文主要是介绍2021-8-17 371. 两整数之和(位运算),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
注:
1.带符号数int如果是负数,并<<,则符号位超出范围,结果是未定义的,需要转化成无符号数unsigned int 超出则抛弃。
2.在计算机系统中,数值一律用补码来表示和存储。原因在于,使用补码,可以将符号位和数值域统一处理;同时,加法和减法也可以统一处理。
题目:
不使用运算符 + 和 - ,计算两整数 a 、b 之和。
示例 1:
输入: a = 1, b = 2
输出: 3
示例 2:
输入: a = -2, b = 3
输出: 1
题解:
位运算中的加法
我们先来观察下位运算中的两数加法,其实来来回回就只有下面这四种:
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 0(进位 1)
仔细一看,这可不就是相同位为 0,不同位为 1 的异或运算结果嘛~
异或和与运算操作
我们知道,在位运算操作中,异或的一个重要特性是无进位加法。我们来看一个例子:
a = 5 = 0101
b = 4 = 0100a ^ b 如下:0 1 0 1
0 1 0 0
-------
0 0 0 1
a ^ b 得到了一个无进位加法结果,如果要得到 a + b 的最终值,我们还要找到进位的数,把这二者相加。在位运算中,我们可以使用与操作获得进位:
a = 5 = 0101
b = 4 = 0100a & b 如下:0 1 0 1
0 1 0 0
-------
0 1 0 0
由计算结果可见,0100 并不是我们想要的进位,1 + 1 所获得的进位应该要放置在它的更高位,即左侧位上,因此我们还要把 0100 左移一位,才是我们所要的进位结果。
那么问题就容易了,总结一下:
- a + b 的问题拆分为 (a 和 b 的无进位结果) + (a 和 b 的进位结果)
- 无进位加法使用异或运算计算得出
- 进位结果使用与运算和移位运算计算得出
- 循环此过程,直到进位为 0
复杂度分析
class Solution {
public:int getSum(int a, int b) {unsigned int icr=static_cast<unsigned int> (a&b);unsigned int result=static_cast<unsigned int> (a^b);while(icr!=0){icr=(icr<<1);int temp=(icr&result);result^=icr;icr=temp;}return result;}
};
这篇关于2021-8-17 371. 两整数之和(位运算)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!