LeetCode中如何不用加減乘除做加法

題目描述

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

• a, b 均可能是負(fù)數(shù)或 0
• 結(jié)果不會溢出 32 位整數(shù)

題目樣例

示例

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

題目思考

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

解決方案

思路

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

復(fù)雜度

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

代碼

python 3

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