使用位運算技巧實現加減乘除

作者：Grey

原文地址：

部落格園：使用位運算技巧實現加減乘除

CSDN：使用位運算技巧實現加減乘除

說明

題目描述見：LeetCode 29. Divide Two Integers

原題目是：要求不使用乘法、除法和 mod 運運算元實現除法。

我們把題目要求提高一點，不用加減乘除和 mod 運運算元號，只使用位運算實現加減乘除法。

實現加法

互斥或（^）運算就是兩個數對應二進位制值的無進位相加，比如a = 13且b = 20，a ^ b的結果如下（用二進位制表示)

13 = 8 + 4 + 1
20 = 16 + 4

  01101
^ 10100
--------
  11001

結果就是:25

思路可以轉換一下，把加法用互斥或替換，得到兩個數二進位制無進位資訊相加的結果。然後把這個結果加上進位資訊，就是兩個數相加的最終結果。

如上例，a ^ b = 25, a和b相加的進位資訊是01000（十進位制就是 8）。25 + 8 = 32，正好是a + b的結果。

抽象一下:

要計算a + b

先算a ^ b = a'

然後得到 a 和 b 相加的進位資訊 b'

則a + b = a' + b'。由於不能用加號，所以，我們只能逐個把進位資訊疊加。

何時會產生進位資訊？

a 和 b 的二進位制對應位置上都是1，則會產生進位

每次處理的進位為(a & b) << 1。

實現程式碼如下

public static int add(int a, int b) {
    int sum = a;
    while (b != 0) {
        sum = a ^ b;
        b = ((a&b)<<1);
        a = sum;
    }
    return sum;
}

實現減法

a - b = a + (-b)，

由於不能出現減號，所以，可以用加法來模擬一個數的相反數，因為

x的相反數等於~x + 1，即add(~x,1)。

所以，減法實現如下

// 實現減法
public static int minus(int a, int b) {
    return add(a, negNum(b));
}
// 某個數n的相反數就是 ~n + 1，由於不能用+號
// 所以是 add(~n,1)
public static int negNum(int n) {
    return add(~n, 1);
}

實現乘法

小學算術計算兩個數的乘法用的是如下方法，比如 a = 12，b = 22，a * b通過如下方式計算

  19
x 22
------
  38
 38
------
 418

同樣方法也適用於二進位制，19 的二進位制是 10011，22 的二進位制是 10110 ,

     10011
x    10110
-------------
     00000
    10011
   10011
  00000
 10011
------------
 110100010

110100010 就是 418。

其本質就是：

b 的二進位制值從右往左開始，如果 b 的某一位是 1 ，則把 a 左移一位的值加到結果中，模擬 1 * a，如果 b 的某一位是0，則 a 左移一位的值不加入結果中。最後累加的結果就是a * b的答案。

位運算實現乘法的完整程式碼如下

    public static int multi(int a, int b) {
        int res = 0;
        while (b != 0) {
            if ((b & 1) != 0) {
                res = add(res, a);
            }
            a <<= 1;
            b >>>= 1;
        }
        return res;
    }

實現除法

實現除法的時候，為了防止溢位，我們首先把所有數先轉換成正數來算。最後在判斷兩個數的符號決定是否把結果取其相反數。

假設 a / b = c，則 a = b * c，用二進位制來說明，假設：

a = b * (2^7) + b * (2^4) + b * (2^1)，則 c 的二進位制一定是10010010。

同理，如果

a = b * (2^3) + b * (2^0)，則 c 的二進位制一定是1001。

抽象一下，如果a = b * (2 ^ m1) + b * (2 ^ m2) + b * (2 ^ m3)，則 c 的 m1 位置，m2 位置，m3 位置一定是1，其他位置都是0。

所以，我們的思路可以轉換成 a 是由幾個 (b * 2的某次方)的結果組成，

使用位運算實現除法的核心程式碼如下：

    // 全部轉成正數來計算
    public static int div(int x, int y) {
        int a = isNeg(x) ? negNum(x) : x;
        int b = isNeg(y) ? negNum(y) : y;
        int res = 0;
        for (int i = 31; i > negNum(1); i = minus(i, 1)) {
            if ((a >> i) >= b) {
                res |= (1 << i);
                a = minus(a, b << i);
            }
        }
        return isNeg(x) ^ isNeg(y) ? negNum(res) : res;
    }
    public static boolean isNeg(int n) {
        return n < 0;
    }

其中

            if ((a >> i) >= b) {
                res |= (1 << i);
                a = minus(a, b << i);
            }

就是讓 a 不斷嘗試其值是否由(b * 2的某個次方)相加得到。

由於有一些特殊情況，比如在 Java 中，int 型別的系統最小值Integer.MIN_VALUE的相反數依然是Integer.MIN_VALUE。

如果a = Integer.MIN_VALUE且b != -1 && b != Integer.MIN_VALUE，則a / b應該通過如下方式來計算，先讓a + 1

然後算(a + 1) / b = c

接著a - (b * c) = d

然後d / b = e

最後c + e = ((a + 1)/b) + ((a - (b * c)) / b) = a / b

即得到 a / b的值。

根據 LeetCode 題目要求，有如下結論：

Integer.MIN_VALUE / (-1) == Integer.MAX_VALUE。

所以除法的主流程程式碼如下（主要是根據題目要求和系統最小值的特殊情況進行了一些邊界討論，見註釋說明內容）

    public static int divide(int dividend, int divisor) {
        if (divisor == Integer.MIN_VALUE) {
            // 任何數（除了系統最小）除以系統最小肯定是0
            // 系統最小除以系統最小肯定是1
            return dividend == Integer.MIN_VALUE ? 1 : 0;
        }
        // 除數不是系統最小
        if (dividend == Integer.MIN_VALUE) {
            if (divisor == negNum(1)) {
                // LeetCode 的題目要求
                return Integer.MAX_VALUE;
            }
            int res = div(add(dividend, 1), divisor);
            return add(res, div(minus(dividend, multi(res, divisor)), divisor));
        }
        // dividend不是系統最小，divisor也不是系統最小
        return div(dividend, divisor);
    }

完整程式碼見

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

    public static int negNum(int n) {
        return add(~n, 1);
    }

    public static int minus(int a, int b) {
        return add(a, negNum(b));
    }

    public static int multi(int a, int b) {
        int res = 0;
        while (b != 0) {
            if ((b & 1) != 0) {
                res = add(res, a);
            }
            a <<= 1;
            b >>>= 1;
        }
        return res;
    }

    public static boolean isNeg(int n) {
        return n < 0;
    }

    public static int div(int a, int b) {
        int x = isNeg(a) ? negNum(a) : a;
        int y = isNeg(b) ? negNum(b) : b;
        int res = 0;
        for (int i = 31; i > negNum(1); i = minus(i, 1)) {
            if ((x >> i) >= y) {
                res |= (1 << i);
                x = minus(x, y << i);
            }
        }
        return isNeg(a) ^ isNeg(b) ? negNum(res) : res;
    }

    public static int divide(int dividend, int divisor) {
        if (divisor == Integer.MIN_VALUE) {
            return dividend == Integer.MIN_VALUE ? 1 : 0;
        }
        // 除數不是系統最小
        if (dividend == Integer.MIN_VALUE) {
            if (divisor == negNum(1)) {
                return Integer.MAX_VALUE;
            }
            int res = div(add(dividend, 1), divisor);
            return add(res, div(minus(dividend, multi(res, divisor)), divisor));
        }
        // dividend不是系統最小，divisor也不是系統最小
        return div(dividend, divisor);
    }
    // div(a,b) a和b都不能是系統最小
}

演演算法和資料結構筆記

參考資料

演演算法和資料結構新手班-左程雲

使用位運算技巧實現加減乘除

使用位運算技巧實現加減乘除

說明

實現加法

實現減法

實現乘法

實現除法

更多

參考資料