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

更新時(shí)間：2023年05月06日 08:42:43 作者：愿榮

這篇文章主要為大家詳細(xì)介紹了Java如何使用位運(yùn)算實(shí)現(xiàn)加減乘除，文中的示例代碼講解詳細(xì)，對(duì)我們深入了解Java有一定的幫助，感興趣的可以了解一下

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

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

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

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

抽象一下:

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

先算 a ^ b = a' 得到的結(jié)果就是無(wú)進(jìn)位相加的結(jié)果, 然后我們?cè)俚玫?a 和 b 相加的進(jìn)位信息 b’, 那么此時(shí) a + b = a' + b' 就是兩數(shù)之和, 但我們這里是不能用加號(hào), 所以我們需要逐個(gè)把進(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)制對(duì)應(yīng)位置上都是1, 才會(huì)產(chǎn)生進(jìn)位, 只需要通過(guò) (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) {
    // 兩個(gè)數(shù)的和等于兩個(gè)數(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ù)相減, 等價(jià)于一個(gè)數(shù)加上另一個(gè)數(shù)的相反數(shù), 即 a - b = a + (-b), 但這里是不能不能出現(xiàn)減號(hào)的, 所以, 可以用加法來(lái)模擬一個(gè)數(shù)的相反數(shù), 因?yàn)?x 的相反數(shù)等于 x 取反再加 1 (~x + 1), 即 add(~x, 1).

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

// 計(jì)算一個(gè)數(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)
    // 一個(gè)數(shù)的相反數(shù)等于這個(gè)數(shù)取反再加1
    return add(a, oppNum(b));
}

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

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

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

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

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

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

其實(shí)這里的二進(jìn)制計(jì)算就對(duì)應(yīng)著這樣一個(gè)過(guò)程, 要求 a * b 的結(jié)果, 就從右往左開(kāi)始遍歷 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 必須是無(wú)符號(hào)右移
        b >>>= 1;
    }
    return res;
}

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

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

假設(shè) a / b = c, 則 a = b * c, 使用位運(yùn)算就需要結(jié)合二進(jìn)制來(lái)思考, 這里假設(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 是由幾個(gè) ( b * 2 的某次方) 的結(jié)果組成.

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

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

其中

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

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

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

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

1.如果兩操作數(shù)都是系統(tǒng)最小值, 結(jié)果就是 1;

2.如果只有除數(shù) (b) 為系統(tǒng)最小值, 結(jié)果就是 0;

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

4.如果被除數(shù) (a) 為系統(tǒng)最小值, 除數(shù)為 -1 和 Integer.MIN_VALUE時(shí) (即a = Integer.MIN_VALUE且b != -1 && b != Integer.MIN_VALUE), a / b應(yīng)該通過(guò)如下方式來(lái)計(jì)算;

可以先讓先讓系統(tǒng)最小值 +1 (a + 1), 此時(shí)就可以按照正常上面的正常流程去計(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

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

// 除法的計(jì)算如果有系統(tǒng)最小值需要進(jìn)行特殊判斷(因?yàn)镮nteger.MAX_VALUE取反再+1得到的還是原來(lái)值), 也就是沒(méi)辦法計(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 的這個(gè)值的, 但力扣系統(tǒng)返回 Integer.MAX_VALUE 就行了
            return Integer.MAX_VALUE;
        } else {
            // 系統(tǒng)最小值沒(méi)法取相反數(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) {
        // 兩個(gè)數(shù)的和等于兩個(gè)數(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ì)算一個(gè)數(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)
        // 一個(gè)數(shù)的相反數(shù)等于這個(gè)數(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 必須是無(wú)符號(hào)右移
            b >>>= 1;
        }
        return res;
    }
    // 不使用算數(shù)運(yùn)算實(shí)現(xiàn)除法
    // 判斷是不是負(fù)數(shù)
    public static boolean isNegavit(int num) {
        return num < 0;
    }
    // 這個(gè)適用于a和b都不是系統(tǒng)最小值的情況下
    public static int div(int a, int b) {
        // 這里的除法一定要保證兩個(gè)數(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 向左移動(dòng)到和 x 最接近的值, 但要滿足 y <= x, 如果是這個(gè)條件下, 也就是讓 y 左移, 可能會(huì)溢出到符號(hào)位, 就可能會(huì)出錯(cuò)
        // 實(shí)際上將 x 向右移動(dòng)到和 y 最接近的值, 移動(dòng)的位數(shù)和上面也是一樣的, 不過(guò)要滿足 x >= y;
        for (int i = 30; i >= 0; i = minus(i, 1)) {
            if ((x >> i) >= y) {
                // 這個(gè)比特位一定是1
                res |= (1 << i);
                // x 減去 y << i;
                x = minus(x, y << i);
            }
        }
        // isNegavit(a) != isNegavit(b) 這個(gè)也可以用 isNegavit(a) ^ isNegavit(b) 來(lái)實(shí)現(xiàn)效果
        return isNegavit(a) != isNegavit(b) ? oppNum(res) : res;
    }
    // 除法的計(jì)算如果有系統(tǒng)最小值需要進(jìn)行特殊判斷(因?yàn)镮nteger.MAX_VALUE取反再+1得到的還是原來(lái)值), 也就是沒(méi)辦法計(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 的這個(gè)值的, 但力扣系統(tǒng)返回 Integer.MAX_VALUE 就行了
                return Integer.MAX_VALUE;
            } else {
                // 系統(tǒng)最小值沒(méi)法取相反數(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)算, 其他可以正常使用, 代碼就簡(jiǎ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 必須是無(wú)符號(hào)右移
            b >>>= 1;
        }
        return res;
    }
    public static int div(int a, int b) {
        // 這里的除法一定要保證兩個(gè)數(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 向左移動(dòng)到和 x 最接近的值, 但要滿足 y <= x, 如果是這個(gè)條件下, 也就是讓 y 左移, 可能會(huì)溢出到符號(hào)位, 就可能會(huì)出錯(cuò)
        // 實(shí)際上將 x 向右移動(dòng)到和 y 最接近的值, 移動(dòng)的位數(shù)和上面也是一樣的, 不過(guò)要滿足 x >= y;
        for (int i = 30; i >= 0; i--) {
            if ((x >> i) >= y) {
                // 這個(gè)比特位一定是1
                res |= (1 << i);
                // x 減去 y << i;
                x -= (y << i);
            }
        }
        // isNegavit(a) != isNegavit(b) 這個(gè)也可以用 isNegavit(a) ^ isNegavit(b) 來(lái)實(shí)現(xiàn)效果
        return isNegavit(a) != isNegavit(b) ? oppNum(res) : res;
    }
    // 除法的計(jì)算如果有系統(tǒng)最小值需要進(jìn)行特殊判斷(因?yàn)镮nteger.MAX_VALUE取反再+1得到的還是原來(lái)值), 也就是沒(méi)辦法計(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 的這個(gè)值的, 但力扣系統(tǒng)返回 Integer.MAX_VALUE 就行了
                return Integer.MAX_VALUE;
            } else {
                // 系統(tǒng)最小值沒(méi)法取相反數(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);
        }
    }
}

上述代碼都是可以通過(guò)OJ的