【LeetCode】371. 两整数之和

August 16, 2018 LeetCode 学习笔记

要求

不使用运算符 + 和-,计算两整数a 、b之和。

示例:
若 a = 1 ,b = 2,返回 3。


首先想到加法器

  1. 半加器

半加器

  1. 全加器

全加器

然后发现 负数不能运算,ok

  1. 补码运算

所谓补码,在二进制中,就是说正数的补码还是其本身,而负数的补码是首位不变,其原码(本身)取反变成反码再加1。或者说成是其绝对值的原码取反再加1。

  1. C++关于负数

c++中的负数是以补码的形式保存 比如 int -1 实际上是 0xFFFFFFFF 而不是0x8000001

(11111111111111111111111111111111)

(1000000000000000000000000001)

负数右移补一,

正数右移补零。

最终代码

class Solution {
public:
    int getSum(int a, int b) {
        long nRet=0;
        long carry=0;
        long pos=0;
        while((a!=0||b!=0)&&pos<32)
        {
            int aa=a&1;
            int bb=b&1;
            int posVal=0;
            posVal=aa^bb^carry;
            carry=(aa&bb|(carry&&(aa^bb)));

            a>>=1;
            b>>=1; 

            posVal<<=pos;
            nRet|=posVal;
            pos++;
        }
        nRet|=(carry<<=pos);
        return nRet;
    }
};

图片外链自维基百科,请确保自己可以访问。

添加新评论