剑指offer——不用加减乘除做加法

迷南。 2022-06-02 01:11 194阅读 0赞

题意：写一个函数，求两个整数之和，要求在函数体内不得使用+、-、\*、/四则运算符号。

分析：之前自己手动yy了一下，直接用二进制进行位运算，然后没考虑负数，直接WA，接着仔细分析，数分四种情况(a>0,b>0;a>=0,b<=0;a<0,b>0;a<0,b<0)，然后计算，注意进位或者借位的情况就OK了，比较复杂。

参考代码：

class Solution {
    public:
        int Add(int num1, int num2)
        {
            int ans = 0;
            int sign = 1;//和的符号位为+
            bool flag = true;//做加法
            if( num1 >= 0 && num2 <= 0)
            {
                num2 = abs(num2);
                flag = false;//做减法
                if( num1 < num2)
                {
                    sign = -1;//符号位为-
                    swap(num1,num2);
                }
            }
            else if( num1 < 0 && num2 > 0)
            {
                num1 = abs(num1);
                flag = false;
                if( num1 > num2)
                    sign = -1;
                else
                    swap(num1,num2);
            }
            else if( num1 < 0 && num2 < 0)
            {
                sign = -1;
                num1 = abs(num1);
                num2 = abs(num2);
            }
    
            bool carry = false;
            bool borrow = false;
            int cnt = 0;
            while( num1 || num2)
            {
                if( ( num1&1) && ( num2&1))//都是1加法进位(如果本身有进位就要计算一下),减法为0(有借位特殊处理)，都是0不用管
                {
                    if( flag)//+
                    {
                        if( carry)
                            ans = ans^(1<<cnt);
                        carry = true;
                    }
                    else
                    {
                        if( borrow)
                            ans = ans^(1<<cnt);
                    }
                }
                else if( ( num1&1) && !( num2&1))//前1后0，
                {
                    if( flag)//+
                    {
                        if( !carry)
                            ans = ans^(1<<cnt);
                    }
                    else//-
                    {
                        if( !borrow)//无借位，直接减
                            ans = ans^(1<<cnt);
                        else
                            borrow = false;
                    }
                }
                else if( !( num1&1) && ( num2&1))//前0后1
                {
                    if( flag)
                    {
                        if( !carry)
                            ans = ans^(1<<cnt);
                    }
                    else
                    {
                        if( !borrow)
                            ans = ans^(1<<cnt);
                        borrow = true;
                    }
                }
                else if( !( num1&1) && !( num2&1))//0 0
                {
                    if( flag)
                    {
                        if( carry)
                        {
                            ans = ans^(1<<cnt);
                            carry = false;
                        }
                    }
                    else
                    {
                        if( borrow)
                            ans = ans^(1<<cnt);
                    }
                }
                cnt++;
                num1 >>= 1;
                num2 >>= 1;
            }
            if( flag && carry)
                ans = ans^(1<<cnt);
            return ans*sign;
        }
    };

但是，发现我的做法好像太复杂了些，代码有点长，然后瞄了一眼百度(QAQ应该先想想思路的，不应该百度= =)，emmm发现有更简单的方法，就是用异或+移位操作了，每次计算得到两个结果，一是两个数进行异或的结果，另一个就是进位的结果，其实还是求这两个得到的数的和，一直循环这个操作指导进位为0，就得到了最终答案。这样处理的话，就不用管正负数了，简洁啊。

class Solution {
    public:
        int Add(int num1, int num2)
        {
            int ans = 0;
            int carry;
            while( true)
            {
                ans = num1^num2;
                carry = (num1&num2)<<1;
                if( !carry)
                    return ans;
                num1 = ans;
                num2 = carry;
            }
        }
    };