題目

難度：★★☆☆☆
類型：數(shù)學

不使用運算符 + 和 - ???????，計算兩整數(shù) ???????a 、b ???????之和。

示例

示例 1:
輸入: a = 1, b = 2
輸出: 3

示例 2:
輸入: a = -2, b = 3
輸出: 1

解答

這道題目就是實現(xiàn)：

class Solution(object):
    def getSum(self, num1, num2):
        return num1 + num2

雖然這么寫肯定是可以通過的，但是這個“+”就是題目想讓我們實現(xiàn)的。

無符號整數(shù)相加

我們先來看一下無符號整數(shù)在計算機內部是如何進行加法計算的。

和十進制相同，二進制也是通過從低位到高位依次相加實現(xiàn)加法計算，這里我們編寫了三個函數(shù)：

1. 補零函數(shù)（add_zero）：為了將兩個二進制數(shù)變成同樣的長度，通過向較小數(shù)高位補零實現(xiàn)；

2. 一位全加器（add_bit）：實現(xiàn)一位的加法計算，這個在數(shù)字電路中是實現(xiàn)加法計算的基礎，它的輸入有三個，其中兩個是加數(shù)bit1和bit2（0或1），另一個是上一位的進位carry，輸出有兩個，一個是當前位的計算結果cur_res，另一個是當前計算的進位（cur_carry），狀態(tài)轉移矩陣為：

3. 一個4字節(jié)全加器（add_unsigned_nums）：通過組合多個一位全加器實現(xiàn)，實現(xiàn)兩個無符號整數(shù)之和。

class Solution(object):
    def getSum(self, a, b):

        def add_zero(num1, num2):
            """
            兩個二進制字符串中較短的最高位補零，補到和較長的一樣長度。
            :param num1:
            :param num2:
            :return:
            """
            if len(num1) > len(num2):
                num2 = '0' * (len(num2) - len(num1)) + num2
            elif len(num2) > len(num1):
                num1 = '0' * (len(num1) - len(num2)) + num1
            return num1, num2

        def add_bit(bit1, bit2, carry):
            """
            模擬數(shù)字電路，我們也來實現(xiàn)一個一位的全加器，這里我們輸入和輸出都是字符串形式。
            :param bit1: 第一個數(shù)，0或1
            :param bit2: 第二個數(shù)，0或1
            :param carry: 上一步的進位
            :return: cur_res: 當前位的計算結果
            :return: cur_carry: 進位
            """
            if bit1 == '0' and bit2 == '0':         # 如果輸入兩個數(shù)均為零
                cur_res = carry                     # 結果即為上一步進位
                cur_carry = '0'                     # 當前進位是零
            elif bit1 == '1' and bit2 == '1':       # 如果輸入兩個數(shù)均為一
                cur_res = carry                     # 結果還是上一步進位
                cur_carry = '1'                     # 當前進位是一
            else:                                   # 如果輸入一個是一，另一個是零
                if carry == '0':                    # 此時如果上一步進位為零
                    cur_res = '1'                   # 當前結果是一
                    cur_carry = '0'                 # 進位是零
                else:                               # 此時如果上一步進位為一
                    cur_res = '0'                   # 當前結果為零
                    cur_carry = '1'                 # 進位為一
            return cur_res, cur_carry               # 返回計算結果和進位

        def add_unsigned_nums(num1, num2):
            """
            相加兩個無符號二進制整數(shù)（字符串）
            :param num1:
            :param num2:
            :return:
            """
            res = ''
            carry = '0'
            for bit1, bit2 in reversed(list(zip(num1, num2))):
                cur_res, carry = add_bit(bit1, bit2, carry)     # 計算當前位
                res = cur_res + res
            if carry == '1':                        # 如果還有進位
                res = carry + res                   # 記得加到最高位
            return res                              # 返回結果

        def add_nums(num1, num2):
            num1, num2 = bin(num1)[2:], bin(num2)[2:]         # 十進制轉二進制（字符串）
            num1, num2 = add_zero(num1, num2)           # 短數(shù)補零與長數(shù)對齊
            res = add_unsigned_nums(num1, num2)         # 二進制求和
            return int(res, base=2)

        return add_nums(a, b)

有符號整數(shù)

我們使用類似的方法，實現(xiàn)有符號32位整數(shù)的相加，這里需要注意的是，32位有符號整數(shù)的范圍是-2^31 ~ 2^31-1，負數(shù)用補碼表示；如果計算結果超過整數(shù)范圍，說明計算結果為負數(shù)，需要進行換算。

下面已經為讀者寫好了函數(shù)，這里我們使用掩碼進行當前計算位的選擇，讀者如果希望觀察計算流程，可以把打印開關（print_log）打開。

def oct2bin(num):
    """
    32位有符號整數(shù)轉為對應的二進制字符串
    :param num:
    :return:
    """
    mask = 0x01
    res = ''
    for i in range(32):
        cur = '1' if num & mask != 0 else '0'
        res = cur + res
        mask = mask << 1
    return res


class Solution(object):
    def getSum(self, num1, num2, print_log=False):

        print('當前加數(shù)為：{}'.format(oct2bin(num1)))
        print('當前加數(shù)為：{}'.format(oct2bin(num2)))
        ans = 0                     # 結果變量
        mask = 0x01                 # 這個掩碼是用來提取指定位的值的
        carry = 0                   # 進位
        for i in range(0, 32):      # 32位中遍歷
            a = num1 & mask         # 提取當前位
            b = num2 & mask         # 提取當前位
            c = carry               # 提取上一步進位
            carry = 0               # 當前步進位歸零
            if a ^ b != 0:          # 如果兩個計算數(shù)中有一個為一，另一個是零
                if c == 1:          # 上一步進位為一
                    carry = 1       # 則當前一定會產生進位，當前位計算結果為零，ans不用動
                else:               # 上一步進位為零
                    ans |= mask     # 當前不產生進位，當前位計算結果為一
            else:                   # 如果兩個計算數(shù)中均為一或者均為零
                if a & mask > 0:    # 研究兩個計算數(shù)均為一的情況
                    carry = 1       # 進位肯定是要的
                if c == 1:          # 如果上一步有一個進位
                    ans |= mask     # 那么當前結果就是一
            mask = mask << 1        # 我們把掩碼向左移動一位，開始研究更高的一位
            if print_log:           # 打印記錄
                print('\n當前遍歷到了從低向高第{}位。'.format(i))
                print('當前掩碼為：{}'.format(oct2bin(mask)))
                print('當前加數(shù)一：{}'.format(oct2bin(a)))
                print('當前加數(shù)二：{}'.format(oct2bin(b)))
                print('當前結果為：{}'.format(oct2bin(ans)))

        if ans > 0x7fffffff:        # 這種情況說明可能得到了負數(shù)
            return ans - 0xffffffff - 1     # 返回負數(shù)的計算結果
        return ans                  # 返回最終結果


if __name__ == "__main__":
    s = Solution()
    print(s.getSum(1, 5, True))

刁鉆技巧

網上流傳一種一句話實現(xiàn)的遞歸調用法，供讀者參考。

class Solution(object):
    def getSum(self, a, b):
        """
        :type a: int
        :type b: int
        :rtype: int
        """
        return a if b == 0 else self.getSum(a ^ b, (a & b) << 1)

如有疑問或建議，歡迎評論區(qū)留言~