Java利用位運(yùn)算實(shí)現(xiàn)比較兩個(gè)數(shù)的大小

更新時(shí)間：2022年08月31日 08:46:44 作者：Grey

這篇文章主要為大家介紹了，在Java中如何不用任何比較判斷符（>,==,<），返回兩個(gè)數(shù)( 32 位整數(shù))中較大的數(shù)，感興趣的可以了解一下

題目要求

如何不要用任何比較判斷符（>,==,<），返回兩個(gè)數(shù)( 32 位整數(shù))中較大的數(shù)。

主要思路

方法1（不考慮溢出）

要比較 a 和 b 的大小，因?yàn)椴荒苡帽容^符號(hào)，我們可以通過(guò) a - b 的符號(hào)位來(lái)判斷，如果 a - b 的符號(hào)位是 1，說(shuō)明 a - b < 0，則 a 小，否則 a 大或者 a 和 b 相等。

如何判斷一個(gè)數(shù)的符號(hào)位是 0 還是 1 ？

由于是 32 位整數(shù)，所以如果將一個(gè)數(shù)右移 31 位，然后和 1 相與(&)，如果得到 1，則這個(gè)數(shù)是負(fù)數(shù)，如果得到 0，則這個(gè)數(shù)是正數(shù)。

舉個(gè)具體例子，如果要求 a 和 b 誰(shuí)大，我們可以先通過(guò)

((a - b) >> 31) & 1 得到一個(gè)值，如果這個(gè)值是 1 ，說(shuō)明 a 小，否則 a 大或者 a 和 b 相等。

由于不能出現(xiàn)比較符號(hào)，所以無(wú)法使用如下代碼

return ((a - b) >> 31) & 1 == 1?b:a;

也無(wú)法使用如下代碼

if (((a - b) >> 31) & 1 == 1){
    return b;
}
return a;

但是我們可以巧妙利用((a - b) >> 31) & 1結(jié)果去構(gòu)造一個(gè)公式，這個(gè)公式可以在((a - b) >> 31) & 1 == 1情況下得到 b，在((a - b) >> 31) & 1 == 0情況下得到 a。

我們可以利用一個(gè)反轉(zhuǎn)函數(shù)

public int flip(int n) {
    return n ^ 1;
}

這個(gè)函數(shù)的作用就是，當(dāng)n == 1時(shí)，返回 0，當(dāng)n == 0時(shí)，返回 1，我們將判斷符號(hào)的結(jié)果flip一次，如下代碼

    public static int sign(int n) {
        return flip((n >> 31) & 1);
    }

這個(gè)方法的作用就是

當(dāng)符號(hào)位是 1 的時(shí)候，返回 0，符號(hào)位是 0 的時(shí)候，返回 1。

這樣flip后，

sign(a - b)如果得到 1，則：a - b > 0，則返回 a。

sign(a - b)如果得到 0，則：a - b <= 0，則返回 b。

公式可以定義成

sign(a - b) * a + flip(sign(a - b)) * b

主函數(shù)直接做如下調(diào)用

public static int getMax1(int a, int b) {
    int c = a - b;
    //當(dāng)符號(hào)位是 1 的時(shí)候，scA = 0，符號(hào)位是 0 的時(shí)候，scA = 1。
    int scA = sign(c);
    // scA = 1 時(shí)，scB = 0，scA = 0時(shí)，scB = 1
    int scB = flip(scA);
    // 如果 scA = 0，說(shuō)明 b 大，直接返回b
    // 如果 scA = 1，說(shuō)明 a 大，直接返回a
    return a * scA + b * scB;
}

這個(gè)方法沒(méi)有考慮溢出的情況，比如

a = 2147483647;
b = -2147480000;

a - b直接就溢出了，后面的算法就都不適用了。

方法2（考慮溢出情況）

那我們可以先比較 a 與 b 兩個(gè)數(shù)的符號(hào)，

會(huì)有如下幾種情況：

情況1：符號(hào)不同，則直接返回符號(hào)為正的那個(gè)數(shù)。

情況2：如果符號(hào)相同，則這種情況下,a - b的值絕對(duì)不會(huì)溢出，那么就看 c 的符號(hào)（c為正返回a，c為負(fù)返回b）

方法2的核心代碼如下

int c = a - b;
int sa = sign(a);
int sb = sign(b);
int sc = sign(c);
int difSab = sa ^ sb;
int sameSab = flip(difSab);
int returnA = difSab * sa + sameSab * sc;
int returnB = flip(returnA);
return a * returnA + b * returnB;

其中: int difSab = sa ^ sb就是判斷 a 和 b 的符號(hào)是否一樣，如果 difSab == 1，則 a 和 b 符號(hào)一樣，如果difSab == 0，則a 和 b符號(hào)不一樣。

只有當(dāng)difSab == 0的時(shí)候，要考慮 c 的符號(hào)。因?yàn)?code>difSab == 0,所以int returnA = 0 * sa + 1 * sc;，即int returnA = sc,如果 sc 為 1，說(shuō)明 c 的符號(hào)是 0，則a - b > 0，返回 a 即可，否則返回 b。

方法1和方法2的完整代碼和測(cè)試代碼如下：

// 不要用任何比較判斷，返回兩個(gè)數(shù)中較大的數(shù)
public class Code_GetMax {

    public static int flip(int n) {
        return n ^ 1;
    }


    public static int sign(int n) {
        return flip((n >> 31) & 1);
    }

    public static int getMax1(int a, int b) {
        int c = a - b;
        int scA = sign(c);
        int scB = flip(scA);
        return a * scA + b * scB;
    }

    public static int getMax2(int a, int b) {
        int c = a - b;
        int sa = sign(a);
        int sb = sign(b);
        int sc = sign(c);
        int difSab = sa ^ sb;
        int sameSab = flip(difSab);
        int returnA = difSab * sa + sameSab * sc;
        int returnB = flip(returnA);
        return a * returnA + b * returnB;
    }

    public static void main(String[] args) {
        int a = -16;
        int b = -19;
        System.out.println(getMax1(a, b));
        System.out.println(getMax2(a, b));
        a = 2147483647;
        b = -2147480000;
        System.out.println(getMax1(a, b)); // wrong answer because of overflow
        System.out.println(getMax2(a, b));

    }
}

到此這篇關(guān)于Java利用位運(yùn)算實(shí)現(xiàn)比較兩個(gè)數(shù)的大小的文章就介紹到這了,更多相關(guān)Java位運(yùn)算內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: