Daily C/C++ 更简单的加法模拟
本题来自leetcode链接
原始的思路就是一位一位的模拟加法器的运算
这样我们从最低位开始,每次维护进位的信息。循环32次即可
这里有一个更巧妙的实现方法,有点并行的那个感觉
先贴代码
unsigned int res = a;
unsigned int nxt = b;
while (nxt) {
unsigned int tmp = (res & nxt) << 1;
res ^= nxt;
nxt = tmp;
}
首先是对于这种位运算我们先转化成无符号数
然后每次计算,对于下一轮的进位信息,我们都这样获得(res & nxt) << 1
他相当与是我们对当前两个数的每一位都进行了一次AND,这样就找到了每一位的进位信息。然后我们左移他,相当于将这个进位的信息转化成真实的数值
下一步的异或操作就是得到当前位。
那么这样我们对于每次计算,就会得到两个新的加数。我们不断的判断,当有一个加数为0的时候,就可以结束加法。这里就直接判断了进位的数
可以这样想,对于最简单的加法器,1 + 1是2,我们会得到原本位的0和进位的1,实际上这个进位的1的含义就是2,而我们可以通过左移前面的1得到这个2
将这种情况拓展到多个位,道理也是一样的
之所以我们要算多次,就是因为每次计算的时候没有算前一位的进位位的影响,这个影响的计算被延迟到了下一次计算。
文章评论