How to use bitwise operations to implement multiplication in Java

Decimal multiplication

For example, 26 * 15, when performing multiplication operations, we generally calculate like this, first multiply 5 by 6 Get 30, write down 0 and put 3 aside, then multiply 5 by 2Get10 Add the previous 3 and write it below to get 130; after calculating 5, calculate 1 Multiply by 6 and 2 respectively and record the result 26 below, then add 130 and 26 Adding (with misalignment) results in 390.

Binary multiplication

After reading the decimal multiplication, let’s look at the binary multiplication. The basic principle is the same, and it is also multiplied by a cross. For example, calculate 5 * 7. The binary system of

5 is 101, the binary system of 7 is 111, let’s look at the binary cross multiplication Law.

You can see that the binary number is 101 and the binary number 111 is calculated in the traditional way, and the result is 100011, and the decimal corresponding to the binary 100011 is 35.
So, in the calculation process, the calculation methods of decimal and binary are the same. Of course, examples and proofs will not be given here.

Idea Analysis

Now that the calculation process is there, how to implement it with code?

Let’s take a look at the binary calculation process in the picture above:

• First use the last digit of binary 1111 Multiply by 101 to get 101.

• Use the second last digit 1 of binary 111 and multiply it by 101 to get 101.

• Use the third last digit of binary 1111 and multiply it by 101 to get 101.

• Perform binary addition of the three 101 obtained to obtain 100011.

Note that the results 101 obtained in steps 2 and 3 have been moved forward one place , equivalent to 1010 and 10100, that is, the final addition calculation is: 10100 1010 101 = 100011.

Let’s look at the calculation of the final addition10100 1010 101 = 100011, that is, as long as we find how to convert the data into the addition of several digits, because it has been implemented before Learn how to use bitwise operations to implement addition operations.

The number of these three numbers 101, 1010, 10100 is exactly the same as the number of binary 111, That is to say, the number of binary numbers (the multiplier 111 at the bottom of the picture above) will produce several numbers when added together. If multiplied by 11111, it will produce 5The numbers are added up.

Let’s look at the relationship before the data:

• The first multiplication result: 101 = 101 0

• The result of the second multiplication: 1111 = 101

• The result of the third multiplication: 100011 = 101

From here we can see that for each calculation, 101 only needs to be moved to the left once. Just add the last calculation result.

So, how do you know how many times to shift left? From the example here, 111 moves to the right once after each calculation, and 101 also moves to the left once, until 111 only has the last digit left. , then just stop the calculation.

Code implementation

According to the above ideas, let’s implement the code:

// 用位运算实现加法
public static int add(int a, int b) {
    int sum = 0;
    while (b != 0) {
        sum = a ^ b;
        b = (a & b) << 1;
        a = sum;
    }
    return sum;
}

// 用位运算实现减法
public static int multi(int a, int b) {
    int res = 0;
    while (b != 0) {
        if ((b & 1) != 0) {
            res = add(res, a);
        }
        a <<= 1;
        b >>>= 1;
    }
    return res;
}

Run the code and see the result:

You can see that the calculation is correct and negative numbers are also supported.

The above is the detailed content of How to use bitwise operations to implement multiplication in Java. For more information, please follow other related articles on the PHP Chinese website!