目錄

• 1 . 實現加法
• 2 . 實現減法
• 3 . 實現乘法
• 4 . 實現除法

在線OJ: LeetCode 29. 兩數相除

原題目的要求是不能使用乘法, 除法和取余運算符實現除法.

在本篇博客中把題目要求提高一點, 這里只使用位運算來實現, 順便的也就把只使用位運算實現加減乘除實現了.

就是兩數之和, 但我們這里是不能用加號, 所以我們需要逐個把進位信息再繼續疊加 (即讓a’ 和 b’ 再繼續運算, 得到進位信息和不進位信息…), 直到進位信息為 0 結束.

那么進位信息如何計算?

只有當 a 和 b 的二進制對應位置上都是1, 才會產生進位, 只需要 通過 (a & b) << 1 就可得到進位結果.

所以, 只使用位運算實現加法的代碼如下:

// 不使用算數運算實現兩數相加
public static int add (int a, int b) {
    // 兩個數的和等于兩個數不進位相加和進位相加的和
    // a ^ b 得到的就是兩數不進位相加的和
    // (a & b) << 1 得到的就是兩數只相加進位的值
    // 一直循環至進位值為0計算結束
    int sum = a;
    while (b != 0) {
        sum = a ^ b;
        b = (a & b) << 1;
        a = sum;
    }
    return sum;
}

2 . 實現減法

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

所以, 只使用位運算實現減法可以在加法代碼的基礎上進行:

// 計算一個數字的相反數
public static int oppNum (int num) {
    return add(~num, 1);
}
// 不使用算數運算實現兩數相減
public static int minus(int a, int b) {
    // a - b 就相當于 a + (-b)
    // 一個數的相反數等于這個數取反再加1
    return add(a, oppNum(b));
}

3 . 實現乘法

看下面計算兩個十進制數的乘法用的方法是不是很熟悉, 以 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.

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

只使用位運算實現乘法的代碼如下:

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

4 . 實現除法

在實現除法的時候, 為了防止溢出, 我們可以先把兩數轉換成正數來進行計算; 最后在計算末尾再判斷兩個數的符號決定是否把由正數計算出來的結果取其相反數.

假設 a / b = c, 則 a = b * c, 使用位運算就需要結合二進制來思考, 這里假設:

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

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

所以, 我們實現除法的思路可以轉換成 a 是由幾個 ( b * 2 的某次方) 的結果組成.

所以, 只使用位運算實現除法的核心代碼如下:

// 判斷是不是負數
public static boolean isNegavit(int num) {
    return num < 0;
}
// 這個適用于a和b都不是系統最小值的情況下
public static int div(int a, int b) {
    // 這里的除法一定要保證兩個數都是正數, 如果有負數在計算邏輯最后加上即可
    int x = isNegavit(a) ? oppNum(a) : a;
    int y = isNegavit(b) ? oppNum(b) : b;
    int res = 0;
    // 計算的是 x / y
    // 每次循環 y 向左移動到和 x 最接近的值, 但要滿足 y <= x, 如果是這個條件下, 也就是讓 y 左移, 可能會溢出到符號位, 就可能會出錯
    // 實際上將 x 向右移動到和 y 最接近的值, 移動的位數和上面也是一樣的, 不過要滿足 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) 來實現效果
    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的某個次方) 相加得到.

但只有上面的實現還不夠, 這里是有一些特殊情況需要考慮的, 比如在 Java 中, int 類型的系統最小值Integer.MIN_VALUE取相反數的結果依然是Integer.MIN_VALUE.

所以, 除法的兩個操作數如果有系統最小值的話需要單獨的進行計算處理.

1.如果兩操作數都是系統最小值, 結果就是 1;

2.如果只有除數 (b) 為系統最小值, 結果就是 0;

3.如果被除數 (a) 為系統最小值, 除數為 -1 時, 根據 LeetCode 題目要求, 結果就是Integer.MIN_VALUE / (-1) == Integer.MAX_VALUE;

4.如果被除數 (a) 為系統最小值, 除數為 -1 和 Integer.MIN_VALUE時 (即a = Integer.MIN_VALUE且b != -1 && b != Integer.MIN_VALUE), a / b應該通過如下方式來計算;

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

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

// 除法的計算如果有系統最小值需要進行特殊判斷(因為Integer.MAX_VALUE取反再+1得到的還是原來值), 也就是沒辦法計算相反數
public static int divide(int a, int b) {
    if (a == Integer.MIN_VALUE && b == Integer.MIN_VALUE) {
        // 如果兩數都是系統最小值
        return 1;
    } else if (b == Integer.MIN_VALUE){
        // 如果除數為系統最小值
        return 0;
    } else if (a == Integer.MIN_VALUE) {
        // 被除數為系統最小值
        // 且除數為-1
        if (b == oppNum(1)) {
            // 答案應該是 Integer.MAX_VALUE + 1 的這個值的, 但力扣系統返回 Integer.MAX_VALUE 就行了
            return Integer.MAX_VALUE;
        } else {
            // 系統最小值沒法取相反數計算
            // 1. c = (Integer.MAX_VALUE + 1) / b , 先讓系統最小值 +1 后再除以 b
            // 2. (Integer.MAX_VALUE - c * b) / b
            // 3. 再將 1 和 2 的結果相加節課
            int c = div(add(a, 1), b);
            return add(c, div(minus(a, mulit(c, b)), b));
        }
    } else {
        // 兩數都不是系統最小值
        return div(a, b);
    }
}

完整實現的代碼如下:

class Solution {
    // 不使用算數運算實現兩數相加
    public static int add (int a, int b) {
        // 兩個數的和等于兩個數不進位相加和進位相加的和
        // a ^ b 得到的就是兩數不進位相加的和
        // (a & b) << 1 得到的就是兩數只相加進位的值
        // 一直循環至進位值為0計算結束
        int sum = a;
        while (b != 0) {
            sum = a ^ b;
            b = (a & b) << 1;
            a = sum;
        }
        return sum;
    }
    // 計算一個數字的相反數
    public static int oppNum (int num) {
        return add(~num, 1);
    }
    // 不使用算數運算實現兩數相減
    public static int minus(int a, int b) {
        // a - b 就相當于 a + (-b)
        // 一個數的相反數等于這個數取反再加1
        return add(a, oppNum(b));
    }
    // 不使用算數運算實現兩數相乘
    public static int mulit (int a, int b) {
        // 就和小學手算十進制類似
        // 讓 a 的每一位去乘 b 的每一位
        int res = 0;
        while (b != 0) {
            if ((b & 1) != 0) {
                res = add(res, a);
            }
            a <<= 1;
            // 要注意 b 必須是無符號右移
            b >>>= 1;
        }
        return res;
    }
    // 不使用算數運算實現除法
    // 判斷是不是負數
    public static boolean isNegavit(int num) {
        return num < 0;
    }
    // 這個適用于a和b都不是系統最小值的情況下
    public static int div(int a, int b) {
        // 這里的除法一定要保證兩個數都是正數, 如果有負數在計算邏輯最后加上即可
        int x = isNegavit(a) ? oppNum(a) : a;
        int y = isNegavit(b) ? oppNum(b) : b;
        int res = 0;
        // 計算的是 x / y
        // 每次循環 y 向左移動到和 x 最接近的值, 但要滿足 y <= x, 如果是這個條件下, 也就是讓 y 左移, 可能會溢出到符號位, 就可能會出錯
        // 實際上將 x 向右移動到和 y 最接近的值, 移動的位數和上面也是一樣的, 不過要滿足 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) 來實現效果
        return isNegavit(a) != isNegavit(b) ? oppNum(res) : res;
    }
    // 除法的計算如果有系統最小值需要進行特殊判斷(因為Integer.MAX_VALUE取反再+1得到的還是原來值), 也就是沒辦法計算相反數
    public static int divide(int a, int b) {
        if (a == Integer.MIN_VALUE && b == Integer.MIN_VALUE) {
            // 如果兩數都是系統最小值
            return 1;
        } else if (b == Integer.MIN_VALUE){
            // 如果除數為系統最小值
            return 0;
        } else if (a == Integer.MIN_VALUE) {
            // 被除數為系統最小值
            // 且除數為-1
            if (b == oppNum(1)) {
                // 答案應該是 Integer.MAX_VALUE + 1 的這個值的, 但力扣系統返回 Integer.MAX_VALUE 就行了
                return Integer.MAX_VALUE;
            } else {
                // 系統最小值沒法取相反數計算
                // 1. c = (Integer.MAX_VALUE + 1) / b , 先讓系統最小值 +1 后再除以 b
                // 2. (Integer.MAX_VALUE - c * b) / b
                // 3. 再將 1 和 2 的結果相加節課
                int c = div(add(a, 1), b);
                return add(c, div(minus(a, mulit(c, b)), b));
            }
        } else {
            // 兩數都不是系統最小值
            return div(a, b);
        }
    }
}

當然, 按照原本的題意, 只是不能使用乘法, 除法和取余運算, 其他可以正常使用, 代碼就簡單了不少, 思路是一樣的, 代碼實現如下:

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) {
        // 就和小學手算十進制類似
        // 讓 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) {
        // 這里的除法一定要保證兩個數都是正數, 如果有負數在計算邏輯最后加上即可
        int x = isNegavit(a) ? oppNum(a) : a;
        int y = isNegavit(b) ? oppNum(b) : b;
        int res = 0;
        // 計算的是 x / y
        // 每次循環 y 向左移動到和 x 最接近的值, 但要滿足 y <= x, 如果是這個條件下, 也就是讓 y 左移, 可能會溢出到符號位, 就可能會出錯
        // 實際上將 x 向右移動到和 y 最接近的值, 移動的位數和上面也是一樣的, 不過要滿足 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) 來實現效果
        return isNegavit(a) != isNegavit(b) ? oppNum(res) : res;
    }
    // 除法的計算如果有系統最小值需要進行特殊判斷(因為Integer.MAX_VALUE取反再+1得到的還是原來值), 也就是沒辦法計算相反數
    public static int divide(int a, int b) {
        if (a == Integer.MIN_VALUE && b == Integer.MIN_VALUE) {
            // 如果兩數都是系統最小值
            return 1;
        } else if (b == Integer.MIN_VALUE) {
            // 如果除數為系統最小值
            return 0;
        } else if (a == Integer.MIN_VALUE) {
            // 被除數為系統最小值
            // 且除數為-1
            if (b == -1) {
                // 答案應該是 Integer.MAX_VALUE + 1 的這個值的, 但力扣系統返回 Integer.MAX_VALUE 就行了
                return Integer.MAX_VALUE;
            } else {
                // 系統最小值沒法取相反數計算
                // 1. c = (Integer.MAX_VALUE + 1) / b , 先讓系統最小值 +1 后再除以 b
                // 2. (Integer.MAX_VALUE - c * b) / b
                // 3. 再將 1 和 2 的結果相加節課
                int c = div(a + 1, b);
                return c + ((a - mulit(c, b)) / b);
            }
        } else {
            // 兩數都不是系統最小值
            return div(a, b);
        }
    }
}

上述代碼都是可以通過OJ的

以上就是Java使用位運算實現加減乘除詳解的詳細內容，更多關于Java位運算的資料請關注其它相關文章！

原文地址：https://blog.csdn.net/Trong_/article/details/130509887