Find the larger of two numbers

Given two 32-bit integers a and b, return the larger number of a and b, requiring no comparison

/**
 * Returns 0 if n is 1, returns 1 if n is 0
 * @param n
 * @return
 */
public static int flip(int n) {
    return n ^ 1;
}

/**
 * Returns the sign of the integer n, 1 for positive numbers and 0, 0 for negative numbers
 * @param n
 * @return
 */
public static int sign(int n) {
    return flip((n >> 31) & 1);
}

/**
 * Returns the largest of two numbers
 * @param a
 * @param b
 * @return
 */
public static int getMax(int a, int b) {
    int c = a - b;
    int sa = sign(a);
    int sb = sign(b);
    int sc = sign(c);
    //difSab=1 sameSab=0 means that the two numbers have different signs
    //difSab=0 sameSab=1 means that the two numbers have the same sign
    int difSab = sa ^ sb;
    int sameSab = flip(difSab);

    int returnA = difSab * sa + sameSab * sc;
    int returnB = flip(returnA);
    return a * returnA + b * returnB;
}

• The flip() function represents the inversion
• The sign() function represents the sign of the integer
• If you just rely on the judgment of the (a-b) symbol, there will be an overflow risk

therefore,

If the a symbol and the b symbol are different (difSab=1 sameSab=0 means that the two numbers are different)

• If a is 0 or positive, then b is negative (sa=1, sb=0), return a
• If a is negative, then b is 0 or positive (sa=0, sb=1), return b

If the sign of a is the same as the sign of b (difSab=0 sameSab=1 means the two numbers have the same sign), the absolute value of a-b will not overflow

• If a-b is 0 or positive (sc=1), return a
• If a-b is negative (sc=0), return b

Addition, subtraction, multiplication and division

Given two 32-bit integers a and b, which can be positive, negative, or 0, do not use arithmetic operations, implement the addition, subtraction, multiplication and division of a and b, but the given a and b perform some results of addition, subtraction, multiplication and division It will lead to data overflow, you can ignore it

addition operation

• a^b is the correct result without considering the carry

• In the case of only counting the carry (only consider what is the value generated by the carry in the process of adding a and b), the result is (a&b)<<1

Because only the addition of 1 and 1 at the i-th bit produces an i-1 carry

• The addition value that does not consider the carry at all and the value that only considers the carry addition is the final result, and it is repeated until the value generated by the carry disappears completely, indicating that the addition is complete.

/**
 * Addition by bitwise operations
 * @param a
 * @param b
 * @return
 */
public static int add(int a, int b) {
    int sum = a;
    while (b != 0) {
        //Add without carry
        sum = a ^ b;
        //carry result
        b = (a & b) << 1;
        a = sum;
    }
    return sum;
}

subtraction

Bit operation realizes subtraction, as long as a+(-b) is realized, and getting an opposite number is the binary inversion of the number +1

/**
 * find the opposite
 * @param n
 * @return
 */
public static int negNum(int n) {
    return add(~n, 1);
}

/**
 * bitwise subtraction
 * @param a
 * @param b
 * @return
 */
public static int minus(int a, int b) {
    return add(a, negNum(b));
}

multiplication

Bit operations implement multiplication.

a x b = a x 2 0 x b 0 + a x 2 1 x b 1 + . . . + a x 2 i x b i + . . . + a x 2 31 x b 31 axb=ax2^0 xb_0 + ax2^1 xb_1 +...+ax2^ixb_i + ... + ax2^{31} xb_{31} axb=ax20xb0​+ax21xb1​+...+ax2ixbi​+...+ax231xb31​, where bi is 0 or 1 representing the value of the i-th bit in the binary representation of the integer b

/**
 * bitwise multiplication
 * @param a
 * @param b
 * @return
 */
public static int multi(int a, int b) {
    int res = 0;
    while (b != 0) {
        if ((b & 1) != 0) {
            res = add(res, a);
        }
        //a is shifted left by 1
        a <<= 1;
        //b shifted right 1 bit
        b >>>= 1;
    }
    return res;
}

division operation

Only suitable for a and b that are not negative First find the largest part that a can contain, then let a subtract this largest part, and then let the remaining a find the second largest part, and find it in turn, if a and b have a negative number or When both are negative, you can turn a and b into positive numbers first, and see the real sign of res after the calculation is complete.

Both a and b are negative numbers, assuming a=286, b=22, res=0

When b is shifted to the left by 31 bits, 30 bits, ..., 4 bits, the result obtained is greater than a, which means that a contains no less than any one of bx232bx2^4^, so these positions of res4res31 are all 0. When b is shifted to the left by 3 bits, the result is 010110000. At this time, a≥b, indicating that a can contain a bx23, that is, res3=1,

the remaining a, i.e. a-bx23

b<<2 is 001011000, at this time a≥b, indicating that the remaining a can contain a bx22, that is, res2=1,

The remaining a, i.e. a-bx23-bx22

After b<<1, it is greater than a, indicating that the remaining a cannot contain bx21

a==b after b<<0, indicating that the remaining a can contain a bx20, that is, res0=1

When the remaining a is subtracted by a b, the result is 0, indicating that a is divided by b, and the result is the res at this time, that is, 000001101=13

The above can only be applied to a and b are not negative, both a and b are negative or there is a negative number that can be converted to a positive number first, and then solve

/**
 * Determine if it is negative
 * @param n
 * @return
 */
public static boolean isNeg(int n) {
    return n < 0;
}

/**
 * Can't handle the case of a negative maximum value
 * @param a
 * @param b
 * @return
 */
public static int div(int a, int b) {
    int x = isNeg(a) ? negNum(a) : a;
    int y = isNeg(b) ? negNum(b) : b;
    int res = 0;
    for (int i = 31; i > -1; i = minus(i, 1)) {
        if ((x >> i) >= y) {
            res |= (1 << i);
            x = minus(x, y << i);
        }
    }
    return isNeg(a) ^ isNeg(b) ? negNum(res) : res;
}

most critical step

The minimum value of a 32-bit integer is -2147483648, the maximum value is 2147483647, and the absolute value of the minimum value is 1 greater than the absolute value of the maximum value.

Therefore, a or b equal to the minimum value cannot be converted into a corresponding positive number

• If neither a nor b is the minimum value, return div(a,b)
• If both a and b are minimum values, a/b==1
• If a is not the minimum value and b is the minimum value, a/b=0
• If a is the minimum value and b is not the minimum value, the processing is as follows

Suppose the maximum value of an integer is 9 and the minimum value is -10

• When a and b ∈ [0,9]
• When a and b ∈ [-9,9]
• when both a and b are -10
• When a∈[-9,9], b=-10
• When a=-10, b∈[-9,9]

1. Suppose a=-10, b=5
2. Calculate (a+1)/b as c -9 / 5
3. Calculate c*b -1 * 5 = -5
4. Calculate a-(c*b), -10-(-5)=-5
5. Calculate (a-(c*b))/b, denoted as rest, -5/5=-1
6. Return the result of c+rest

/**
 * bitwise division
 * @param a
 * @param b
 * @return
 */
public static int divide(int a, int b) {
    if (b == 0) {
        throw new RuntimeException("divisor is 0");
    }
    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) {
        //res=(a+1)/b
        int res = div(add(a, 1), b);
        //res+(a-res*b)/b
        return add(res, div(minus(a, multi(res, b)), b));
    } else {
        return div(a, b);
    }
}