Integer multiplication without using multiply operator

Question

I wrote a method that multiplies two integers. Is there a faster approach that doesn't use the * operator?

The method mult(a, b) multiplies two arbitrary integers. Is there a quicker way to multiply two numbers, without using * in java?

static int mult(int a, int b) {
    if (a > b)
        return recMult(a, b);
    return recMult(b, a);
}

static int recMult(int max, int min) {
    if (min <= 1)
        return min == 1 ? max : 0;
    int cntOfMin = 0, i = 1;
    while ((i = i << 1) <= min)
        cntOfMin++;
    return (max << cntOfMin) + recMult(max, min - (1 << cntOfMin));
}

This method doesn't work on negative numbers and doesn't handle overflows.

Answer 1

Your heuristic is not optimal. recMult is using binary arithmetic to multiply two numbers. It recurses a number of times based on the number of 1-bits in the second number. You pass in the smaller of the two numbers as the second number, but there is no guarantee the smaller number has fewer 1-bits.

Consider 8 * 7, or in binary, 1000 * 111. The 7 is the smaller number, so you use it as the second argument, and you compute (8 << 2) + (8 << 1) + (8 << 0) + 0. If you had chosen to 8 as the second argument, you would have computed (7 << 3) + 0 ... far fewer operations.

The function Integer.bitCount(int i) returns the number of 1-bits in an integer. Using this, we could rewrite mult(int a, int b) as follows:

static int mult(int a, int b) {
    if (Integer.bitCount(a) > Integer.bitCount(b))
        return recMult(a, b);
    return recMult(b, a);
}

The result should be faster.

Similarly, Java provides several functions in the Integer class which can directly extract the 1-bits found in an integer. These are .lowestOneBit(i), .highestOneBit(i), .numberOfLeadingZeros(i), and .numberOfTrailingZeros(i). The last function is most useful here, as the number of trailing zeros corresponds to the bit position of the least significant 1-bit. For example, 8, or 1000 has 3 trailing zeros, and (1 << 3) == 8.

Using this to simplify rectMult(), we could get something like:

private static int recMult(int multiplicand, int multiplier) {
    int product = 0;
    while (multiplier != 0) {
        int shift = Integer.numberTrailingZeros(multiplier);
        product += multiplicand << shift;
        multiplier -= 1 << shift;
    }
    return product;
}

Since the second number is no longer guaranteed to be the smaller of the two, I've renamed max and min to multiplicand and multiplier.

I've also replaced the recursion with a simple loop, which should additionally speed things up.

Additionally, I've declared this helper function private, since it is unlikely other classes will use it.