題目描述

寫一個函數，求兩個整數之和，要求在函數體內不得使用 “+”、“-”、“*”、“/” 四則運算符號。

• a, b 均可能是負數或 0
• 結果不會溢出 32 位整數

題目樣例

示例

• 輸入: a = 1, b = 1
• 輸出: 2

題目思考

1. 不能用四則運算, 那還能用哪些運算符來實現呢?

解決方案

思路

• 相比昨天的題目                     劍指 Offer 64. 求 1+2+…+n - leetcode 劍指 offer 系列, 這道題目限制少了很多, 至少循環/條件判斷/位運算這些都能用了
• 我們先來嘗試分析數字的二進制表示, 看看能否用位運算來替代加法
• 如果某一位的兩個數字都是 1, 那么這一位的加法就會產生進位, 所以                     與可以用來計算進位, 而且顯然進位是要左移一位的
• 接下來考慮如何得到當前位的加法結果.                     異或在兩個數字都為 1 或者都為 0 的情況下結果是 0, 否則結果是 1, 換言之                     異或就是不帶進位的加法
• 將上面兩步結合在一起, 我們就能把                     a+b 轉換成                     ((a&b)<<1)+(a^b), 雖然這里仍然有加號, 但是我們將其置為新的 a 和 b, 循環這個過程, 直到進位變成 0, 這樣最終異或結果就是兩者之和了
• 注意最終進位一定能變成 0, 這是因為如果有進位的話, 進位是會不斷左移的, 而題目保證最終結果不會溢出, 那么經過若干次循環后, 一定會達到一個不需要進位的狀態, 不然無限左移就會溢出了
• C++/JAVA 等語言分析到這里就 OK 了, 但 python 需要特別處理負數問題. 因為 python 的負數表示方法不是像其他語言那樣的 32 位補碼, 而是更高位也全是 1, 這樣在處理負數的時候必須手動模擬 32 位補碼, 才能正確得出結果, 不然最后結果就不滿足 python 正確的負數表示方式, 而變成無符號正數了
• 所以我們需要先將負數轉成 32 位補碼 (                     &0xFFFFFFFF, 正數仍為自身, 負數相當于 32 位補碼形式, 因為去掉了更高位上的 1), 然后利用上述結果求完之后, 如果結果是負數(                     >0x7FFFFFFF)的話再轉成正常的 python 負數表示方式(                     ~(a ^ 0xFFFFFFFF), 即先對低 32 位的取反, 更高位不變, 然后整體再取反, 從而將大于等于 32 位的數字重新轉成 1)
• 下面代碼額外列出了 Java 版本, 方便大家對比. Java 的負數就是 32 位補碼表示, 所以不需要額外進行處理

復雜度

• 時間復雜度 O(logN): 最多需要遍歷所有位數, 數字 N 的位數為 logN
• 空間復雜度 O(1): 只需要維護常數個變量

代碼

python 3

class Solution:
    def add(self, a: int, b: int) -> int:
        # 32位數掩碼
        mask = 0XFFFFFFFF
        # 32位數的最大正數
        posMx = 0X7FFFFFFF
        while b != 0:
            # a是不帶進位的和, 都要轉成32位整數
            # b是進位, 都要轉成32位整數
            # 循環直到進位為0, 那么a就是最終結果
            smwithoutcarry = (a ^ b) & mask
            carry = ((a & b) << 1) & mask
            a, b = smwithoutcarry, carry
        # 最終如果是32位負數的話, 需要將其轉回python正常的負數表示形式(高于32位的全是1, 而不是32位負數那樣更高位全為0), 做法是先對低 32 位的取反, 更高位不變, 然后整體再取反, 從而將大于等于 32 位的數字重新轉成 1
        return a if a <= posMx else ~(a ^ mask)

Java

class Solution {
    public int add(int a, int b) {
        while (b != 0)
        {
            int smwithoutcarry = a ^ b;
            int carry = (a & b) << 1;
            a = smwithoutcarry;
            b = carry;
        }
        return a;
    }
}