只使用位運(yùn)算實(shí)現(xiàn)加減乘除

這篇具有很好參考價值的文章主要介紹了只使用位運(yùn)算實(shí)現(xiàn)加減乘除。希望對大家有所幫助。如果存在錯誤或未考慮完全的地方，請大家不吝賜教，您也可以點(diǎn)擊"舉報違法"按鈕提交疑問。

在線OJ: LeetCode 29. 兩數(shù)相除

原題目的要求是不能使用乘法, 除法和取余運(yùn)算符實(shí)現(xiàn)除法.

在本篇博客中把題目要求提高一點(diǎn), 這里只使用位運(yùn)算來實(shí)現(xiàn), 順便的也就把只使用位運(yùn)算實(shí)現(xiàn)加減乘除實(shí)現(xiàn)了.

只使用位運(yùn)算實(shí)現(xiàn)加減乘除

1 . 實(shí)現(xiàn)加法

首先我們需要知道兩數(shù)之和可以是兩個數(shù)位相加和不進(jìn)位相加之和, 而兩數(shù)進(jìn)行異或(^)運(yùn)算其實(shí)就是兩個數(shù)對應(yīng)二進(jìn)制值的無進(jìn)位相加.

我們可以把思路可以轉(zhuǎn)換一下, 把加法用異或替換, 如果我們能夠得到兩個數(shù)相加的二進(jìn)制進(jìn)位信息為0, 那么此時的無進(jìn)位結(jié)果就是兩數(shù)相加的最終結(jié)果了.

只有二進(jìn)制無進(jìn)位信息, 相加的結(jié)果; 然后把這個結(jié)果加上進(jìn)位信息, 就是兩個數(shù)相加的最終結(jié)果.

抽象一下:

我們要計(jì)算 a + b

先算 a ^ b = a' 得到的結(jié)果就是無進(jìn)位相加的結(jié)果, 然后我們再得到 a 和 b 相加的進(jìn)位信息 b’, 那么此時 a + b = a' + b' 就是兩數(shù)之和, 但我們這里是不能用加號, 所以我們需要逐個把進(jìn)位信息再繼續(xù)疊加 (即讓a’ 和 b’ 再繼續(xù)運(yùn)算, 得到進(jìn)位信息和不進(jìn)位信息…), 直到進(jìn)位信息為 0 結(jié)束.

那么進(jìn)位信息如何計(jì)算?

只有當(dāng) a 和 b 的二進(jìn)制對應(yīng)位置上都是1, 才會產(chǎn)生進(jìn)位, 只需要通過 (a & b) << 1 就可得到進(jìn)位結(jié)果.

所以, 只使用位運(yùn)算實(shí)現(xiàn)加法的代碼如下:

// 不使用算數(shù)運(yùn)算實(shí)現(xiàn)兩數(shù)相加
public static int add (int a, int b) {
    // 兩個數(shù)的和等于兩個數(shù)不進(jìn)位相加和進(jìn)位相加的和
    // a ^ b 得到的就是兩數(shù)不進(jìn)位相加的和
    // (a & b) << 1 得到的就是兩數(shù)只相加進(jìn)位的值

    // 一直循環(huán)至進(jìn)位值為0計(jì)算結(jié)束
    int sum = a;
    while (b != 0) {
        sum = a ^ b;
        b = (a & b) << 1;
        a = sum;
    }
    return sum;
}

2 . 實(shí)現(xiàn)減法

兩數(shù)相減, 等價于一個數(shù)加上另一個數(shù)的相反數(shù), 即 a - b = a + (-b), 但這里是不能不能出現(xiàn)減號的, 所以, 可以用加法來模擬一個數(shù)的相反數(shù), 因?yàn)?x 的相反數(shù)等于 x 取反再加 1 (~x + 1), 即 add(~x, 1).

所以, 只使用位運(yùn)算實(shí)現(xiàn)減法可以在加法代碼的基礎(chǔ)上進(jìn)行:

// 計(jì)算一個數(shù)字的相反數(shù)
public static int oppNum (int num) {
    return add(~num, 1);
}

// 不使用算數(shù)運(yùn)算實(shí)現(xiàn)兩數(shù)相減
public static int minus(int a, int b) {
    // a - b 就相當(dāng)于 a + (-b)
    // 一個數(shù)的相反數(shù)等于這個數(shù)取反再加1
    return add(a, oppNum(b));
}

3 . 實(shí)現(xiàn)乘法

看下面計(jì)算兩個十進(jìn)制數(shù)的乘法用的方法是不是很熟悉, 以 a = 12, b = 22 為例, a * b 通過如下方式計(jì)算;

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

這樣的方法也適用于二進(jìn)制, 19 的二進(jìn)制是 10011, 22 的二進(jìn)制是 10110, 計(jì)算過程如下;

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

得到的計(jì)算結(jié)果 110100010 就是 418.

其實(shí)這里的二進(jìn)制計(jì)算就對應(yīng)著這樣一個過程, 要求 a * b 的結(jié)果, 就從右往左開始遍歷 b 的每一位二進(jìn)制值, 如果 b 的第 i 位是 1, 則把 a 左移 i 位的累值加到結(jié)果中; 如果 b 的第 i 位是 0, 不需要處理, 最后累加完的結(jié)果就是 a * b 的答案.

只使用位運(yùn)算實(shí)現(xiàn)乘法的代碼如下:

// 不使用算數(shù)運(yùn)算實(shí)現(xiàn)兩數(shù)相乘
public static int mulit (int a, int b) {
    // 就小學(xué)手算十進(jìn)制類似
    // 讓 a 的每一位去乘 b 的每一位
    int res = 0;
    while (b != 0) {
        if ((b & 1) != 0) {
            res = add(res, a);
        }
        a <<= 1;
        // 要注意 b 必須是無符號右移
        b >>>= 1;
    }
    return res;
}

4 . 實(shí)現(xiàn)除法

在實(shí)現(xiàn)除法的時候, 為了防止溢出, 我們可以先把兩數(shù)轉(zhuǎn)換成正數(shù)來進(jìn)行計(jì)算; 最后在計(jì)算末尾再判斷兩個數(shù)的符號決定是否把由正數(shù)計(jì)算出來的結(jié)果取其相反數(shù).

假設(shè) a / b = c, 則 a = b * c, 使用位運(yùn)算就需要結(jié)合二進(jìn)制來思考, 這里假設(shè):

a = b * (2^7) + b * (2^4) + b * (2^1), 則 c 的二進(jìn)制一定是10010010.

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

所以, 我們實(shí)現(xiàn)除法的思路可以轉(zhuǎn)換成 a 是由幾個 ( b * 2 的某次方) 的結(jié)果組成.

所以, 只使用位運(yùn)算實(shí)現(xiàn)除法的核心代碼如下:

// 判斷是不是負(fù)數(shù)
public static boolean isNegavit(int num) {
    return num < 0;
}
// 這個適用于a和b都不是系統(tǒng)最小值的情況下
public static int div(int a, int b) {
    // 這里的除法一定要保證兩個數(shù)都是正數(shù), 如果有負(fù)數(shù)在計(jì)算邏輯最后加上即可
    int x = isNegavit(a) ? oppNum(a) : a;
    int y = isNegavit(b) ? oppNum(b) : b;
    int res = 0;
    // 計(jì)算的是 x / y
    // 每次循環(huán) y 向左移動到和 x 最接近的值, 但要滿足 y <= x, 如果是這個條件下, 也就是讓 y 左移, 可能會溢出到符號位, 就可能會出錯
    // 實(shí)際上將 x 向右移動到和 y 最接近的值, 移動的位數(shù)和上面也是一樣的, 不過要滿足 x >= y;
    for (int i = 30; i >= 0; i = minus(i, 1)) {
        if ((x >> i) >= y) {
            // 這個比特位一定是1
            res |= (1 << i);
            // x 減去 y << i;
            x = minus(x, y << i);
        }
    }
    // isNegavit(a) != isNegavit(b) 這個也可以用 isNegavit(a) ^ isNegavit(b) 來實(shí)現(xiàn)效果
    return isNegavit(a) != isNegavit(b) ? oppNum(res) : res;
}

其中

if ((x >> i) >= y) {
    // 這個比特位一定是1
    res |= (1 << i);
    // x 減去 y << i;
    x = minus(x, y << i);
}

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

但只有上面的實(shí)現(xiàn)還不夠, 這里是有一些特殊情況需要考慮的, 比如在 Java 中, int 類型的系統(tǒng)最小值Integer.MIN_VALUE取相反數(shù)的結(jié)果依然是Integer.MIN_VALUE.

所以, 除法的兩個操作數(shù)如果有系統(tǒng)最小值的話需要單獨(dú)的進(jìn)行計(jì)算處理.

如果兩操作數(shù)都是系統(tǒng)最小值, 結(jié)果就是 1;
如果只有除數(shù) (b) 為系統(tǒng)最小值, 結(jié)果就是 0;
如果被除數(shù) (a) 為系統(tǒng)最小值, 除數(shù)為 -1 時, 根據(jù) LeetCode 題目要求, 結(jié)果就是Integer.MIN_VALUE / (-1) == Integer.MAX_VALUE;
如果被除數(shù) (a) 為系統(tǒng)最小值, 除數(shù)為 -1 和 Integer.MIN_VALUE時 (即a = Integer.MIN_VALUE且b != -1 && b != Integer.MIN_VALUE), a / b應(yīng)該通過如下方式來計(jì)算;

可以先讓先讓系統(tǒng)最小值 +1 (a + 1), 此時就可以按照正常上面的正常流程去計(jì)算除法了, 即(a + 1) / b = c.
接著計(jì)算a - (b * c) = d, 得到由于 a + 1 少/多算的.
然后d / b = e
最后將 c 和 e 相加就得到了 a / b 的值, c + e = ((a + 1)/b) + ((a - (b * c)) / b) = a / b

除了這些特殊, 就是正常的流程了, 所以, 加上針對系統(tǒng)最小值的特殊判斷的代碼如下:

// 除法的計(jì)算如果有系統(tǒng)最小值需要進(jìn)行特殊判斷(因?yàn)镮nteger.MAX_VALUE取反再+1得到的還是原來值), 也就是沒辦法計(jì)算相反數(shù)
public static int divide(int a, int b) {
    if (a == Integer.MIN_VALUE && b == Integer.MIN_VALUE) {
        // 如果兩數(shù)都是系統(tǒng)最小值
        return 1;
    } else if (b == Integer.MIN_VALUE){
        // 如果除數(shù)為系統(tǒng)最小值
        return 0;
    } else if (a == Integer.MIN_VALUE) {
        // 被除數(shù)為系統(tǒng)最小值

        // 且除數(shù)為-1
        if (b == oppNum(1)) {
            // 答案應(yīng)該是 Integer.MAX_VALUE + 1 的這個值的, 但力扣系統(tǒng)返回 Integer.MAX_VALUE 就行了
            return Integer.MAX_VALUE;
        } else {
            // 系統(tǒng)最小值沒法取相反數(shù)計(jì)算
            // 1. c = (Integer.MAX_VALUE + 1) / b , 先讓系統(tǒng)最小值 +1 后再除以 b
            // 2. (Integer.MAX_VALUE - c * b) / b
            // 3. 再將 1 和 2 的結(jié)果相加節(jié)課
            int c = div(add(a, 1), b);
            return add(c, div(minus(a, mulit(c, b)), b));
        }
    } else {
        // 兩數(shù)都不是系統(tǒng)最小值
        return div(a, b);
    }
}

完整實(shí)現(xiàn)的代碼如下:

class Solution {
    // 不使用算數(shù)運(yùn)算實(shí)現(xiàn)兩數(shù)相加
    public static int add (int a, int b) {
        // 兩個數(shù)的和等于兩個數(shù)不進(jìn)位相加和進(jìn)位相加的和
        // a ^ b 得到的就是兩數(shù)不進(jìn)位相加的和
        // (a & b) << 1 得到的就是兩數(shù)只相加進(jìn)位的值

        // 一直循環(huán)至進(jìn)位值為0計(jì)算結(jié)束
        int sum = a;
        while (b != 0) {
            sum = a ^ b;
            b = (a & b) << 1;
            a = sum;
        }
        return sum;
    }

    // 計(jì)算一個數(shù)字的相反數(shù)
    public static int oppNum (int num) {
        return add(~num, 1);
    }


    // 不使用算數(shù)運(yùn)算實(shí)現(xiàn)兩數(shù)相減
    public static int minus(int a, int b) {
        // a - b 就相當(dāng)于 a + (-b)
        // 一個數(shù)的相反數(shù)等于這個數(shù)取反再加1
        return add(a, oppNum(b));
    }

    // 不使用算數(shù)運(yùn)算實(shí)現(xiàn)兩數(shù)相乘
    public static int mulit (int a, int b) {
        // 就和小學(xué)手算十進(jìn)制類似
        // 讓 a 的每一位去乘 b 的每一位
        int res = 0;
        while (b != 0) {
            if ((b & 1) != 0) {
                res = add(res, a);
            }
            a <<= 1;
            // 要注意 b 必須是無符號右移
            b >>>= 1;
        }
        return res;
    }

    // 不使用算數(shù)運(yùn)算實(shí)現(xiàn)除法

    // 判斷是不是負(fù)數(shù)
    public static boolean isNegavit(int num) {
        return num < 0;
    }
    // 這個適用于a和b都不是系統(tǒng)最小值的情況下
    public static int div(int a, int b) {
        // 這里的除法一定要保證兩個數(shù)都是正數(shù), 如果有負(fù)數(shù)在計(jì)算邏輯最后加上即可
        int x = isNegavit(a) ? oppNum(a) : a;
        int y = isNegavit(b) ? oppNum(b) : b;
        int res = 0;
        // 計(jì)算的是 x / y
        // 每次循環(huán) y 向左移動到和 x 最接近的值, 但要滿足 y <= x, 如果是這個條件下, 也就是讓 y 左移, 可能會溢出到符號位, 就可能會出錯
        // 實(shí)際上將 x 向右移動到和 y 最接近的值, 移動的位數(shù)和上面也是一樣的, 不過要滿足 x >= y;
        for (int i = 30; i >= 0; i = minus(i, 1)) {
            if ((x >> i) >= y) {
                // 這個比特位一定是1
                res |= (1 << i);
                // x 減去 y << i;
                x = minus(x, y << i);
            }
        }
        // isNegavit(a) != isNegavit(b) 這個也可以用 isNegavit(a) ^ isNegavit(b) 來實(shí)現(xiàn)效果
        return isNegavit(a) != isNegavit(b) ? oppNum(res) : res;
    }
    // 除法的計(jì)算如果有系統(tǒng)最小值需要進(jìn)行特殊判斷(因?yàn)镮nteger.MAX_VALUE取反再+1得到的還是原來值), 也就是沒辦法計(jì)算相反數(shù)
    public static int divide(int a, int b) {
        if (a == Integer.MIN_VALUE && b == Integer.MIN_VALUE) {
            // 如果兩數(shù)都是系統(tǒng)最小值
            return 1;
        } else if (b == Integer.MIN_VALUE){
            // 如果除數(shù)為系統(tǒng)最小值
            return 0;
        } else if (a == Integer.MIN_VALUE) {
            // 被除數(shù)為系統(tǒng)最小值

            // 且除數(shù)為-1
            if (b == oppNum(1)) {
                // 答案應(yīng)該是 Integer.MAX_VALUE + 1 的這個值的, 但力扣系統(tǒng)返回 Integer.MAX_VALUE 就行了
                return Integer.MAX_VALUE;
            } else {
                // 系統(tǒng)最小值沒法取相反數(shù)計(jì)算
                // 1. c = (Integer.MAX_VALUE + 1) / b , 先讓系統(tǒng)最小值 +1 后再除以 b
                // 2. (Integer.MAX_VALUE - c * b) / b
                // 3. 再將 1 和 2 的結(jié)果相加節(jié)課
                int c = div(add(a, 1), b);
                return add(c, div(minus(a, mulit(c, b)), b));
            }
        } else {
            // 兩數(shù)都不是系統(tǒng)最小值
            return div(a, b);
        }
    }
}

當(dāng)然, 按照原本的題意, 只是不能使用乘法, 除法和取余運(yùn)算, 其他可以正常使用, 代碼就簡單了不少, 思路是一樣的, 代碼實(shí)現(xiàn)如下:

class Solution29 {
    public static boolean isNegavit(int num) {
        return num < 0;
    }
    public static int oppNum (int num) {
        return (~num) + 1;
    }

    public static int mulit (int a, int b) {
        // 就和小學(xué)手算十進(jìn)制類似
        // 讓 a 的每一位去乘 b 的每一位
        int res = 0;
        while (b != 0) {
            if ((b & 1) != 0) {
                res += a;
            }
            a <<= 1;
            // 要注意 b 必須是無符號右移
            b >>>= 1;
        }
        return res;
    }
    public static int div(int a, int b) {
        // 這里的除法一定要保證兩個數(shù)都是正數(shù), 如果有負(fù)數(shù)在計(jì)算邏輯最后加上即可
        int x = isNegavit(a) ? oppNum(a) : a;
        int y = isNegavit(b) ? oppNum(b) : b;
        int res = 0;
        // 計(jì)算的是 x / y
        // 每次循環(huán) y 向左移動到和 x 最接近的值, 但要滿足 y <= x, 如果是這個條件下, 也就是讓 y 左移, 可能會溢出到符號位, 就可能會出錯
        // 實(shí)際上將 x 向右移動到和 y 最接近的值, 移動的位數(shù)和上面也是一樣的, 不過要滿足 x >= y;
        for (int i = 30; i >= 0; i--) {
            if ((x >> i) >= y) {
                // 這個比特位一定是1
                res |= (1 << i);
                // x 減去 y << i;
                x -= (y << i);
            }
        }
        // isNegavit(a) != isNegavit(b) 這個也可以用 isNegavit(a) ^ isNegavit(b) 來實(shí)現(xiàn)效果
        return isNegavit(a) != isNegavit(b) ? oppNum(res) : res;
    }

    // 除法的計(jì)算如果有系統(tǒng)最小值需要進(jìn)行特殊判斷(因?yàn)镮nteger.MAX_VALUE取反再+1得到的還是原來值), 也就是沒辦法計(jì)算相反數(shù)
    public static int divide(int a, int b) {
        if (a == Integer.MIN_VALUE && b == Integer.MIN_VALUE) {
            // 如果兩數(shù)都是系統(tǒng)最小值
            return 1;
        } else if (b == Integer.MIN_VALUE) {
            // 如果除數(shù)為系統(tǒng)最小值
            return 0;
        } else if (a == Integer.MIN_VALUE) {
            // 被除數(shù)為系統(tǒng)最小值

            // 且除數(shù)為-1
            if (b == -1) {
                // 答案應(yīng)該是 Integer.MAX_VALUE + 1 的這個值的, 但力扣系統(tǒng)返回 Integer.MAX_VALUE 就行了
                return Integer.MAX_VALUE;
            } else {
                // 系統(tǒng)最小值沒法取相反數(shù)計(jì)算
                // 1. c = (Integer.MAX_VALUE + 1) / b , 先讓系統(tǒng)最小值 +1 后再除以 b
                // 2. (Integer.MAX_VALUE - c * b) / b
                // 3. 再將 1 和 2 的結(jié)果相加節(jié)課
                int c = div(a + 1, b);
                return c + ((a - mulit(c, b)) / b);
            }
        } else {
            // 兩數(shù)都不是系統(tǒng)最小值
            return div(a, b);
        }
    }
}