Java uses bit operations to compare the size of two numbers

Question Requirements

How to avoid using any comparison judgment (>,==,<), returns the larger number of two numbers (32-bit integers).

Main ideas

Method 1 (no overflow consideration)

To compare the sizes of a and b, because we cannot use the comparison symbols, we can judge by the sign bits of a - b. If the sign bits of a - b are 1, it means that a - b < 0, then a is small, otherwise a is large or a and b are equal.

How to determine whether the sign bit of a number is 0 or 1?

Since it is a 32-bit integer, if you shift a number right by 31 bits, then add it to 1 (&), if you get 1, then this number is a negative number, if you get 0, then this number is a positive number.

To give a specific example, if we ask who is bigger, we can pass first

((a - b) >> 31) & 1Get a value. If this value is 1, it means that a is small, otherwise a is large or a and b are equal.

Since comparison symbols cannot appear, the following code cannot be used

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

The following code cannot be used

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

But we can use it ingeniously((a - b) >> 31) & 1As a result, construct a formula, which can be((a - b) >> 31) & 1 == 1In case of b,((a - b) >> 31) & 1 == 0In the case, get a.

We can use an inversion function

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

The function of this function is,n == 1When, return 0, whenn == 0When returning 1, we will judge the result of the symbolflipOnce, the following code

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

The purpose of this method is

When the sign bit is 1, return 0, and when the sign bit is 0, return 1.

soflipback,

sign(a - b)If you get 1, then:a - b > 0, then returns a.

sign(a - b)If you get 0, then:a - b <= 0, then return b.

The formula can be defined as

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

The main function is called directly as follows

public static int getMax1(int a, int b) {
    int c = a - b;
    //When the sign bit is 1, scA = 0, and when the sign bit is 0, scA = 1.    int scA = sign(c);
    // When scA = 1, scB = 0, when scA = 0, scB = 1    int scB = flip(scA);
    // If scA = 0, it means b is large, and b is directly returned    // If scA = 1, it means that a is large and returns a directly    return a * scA + b * scB;
}

This method does not consider overflow, for example

a = 2147483647;
b = -2147480000;

a - bIt will overflow directly, and the subsequent algorithms will not apply.

Method 2 (consider overflow)

Then we can first compare the symbols of the two numbers a and b.

There will be several situations as follows:

Case 1: Different symbols will directly return the number with the positive symbol.

Case 2: If the symbols are the same, in this case,a - bThe value of the quotient will never overflow, so look at the symbol of c (c is positive and returns a, c is negative and returns b)

The core code of method 2 is as follows

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;

in:int difSab = sa ^ sbIt is to judge whether the symbols of a and b are the same, ifdifSab == 1, then a and b symbols are the same as those of b, ifdifSab == 0, then the symbols a and b are different.

Only whendifSab == 0When , consider the symbol of c. becausedifSab == 0,soint returnA = 0 * sa + 1 * sc;,Right nowint returnA = sc,If sc is 1, it means that the symbol of c is 0, thena - b > 0, return a, otherwise return b.

The complete code and test code for Method 1 and Method 2 are as follows:

// Do not use any comparison to judge, return the larger number of the two numberspublic 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;
        (getMax1(a, b));
        (getMax2(a, b));
        a = 2147483647;
        b = -2147480000;
        (getMax1(a, b)); // wrong answer because of overflow
        (getMax2(a, b));

    }
}

This is the end of this article about Java using bit operations to compare the size of two numbers. For more related Java bit operations, please search for my previous articles or continue browsing the related articles below. I hope everyone will support me in the future!