Is there an algorithm to decide if a * b fits within the possible values of an integer? (without casting to a wider type)

Question

Hi all I was wondering if there is a way to implement this method without casting to a wider data type (e.g. long, double, etc)?

CanTimes(int a, int b){
    returns true if a * b is within the range of -2^31 to 2^31-1, else false;
}

For example, we could implement one for the method CanAdd (without casts) as such:

    public static boolean CanPlus(int a, int b) {
        if (b >= 0) {
            return a <= Integer.MAX_VALUE - b
        } else {
            return a >= Integer.MIN_VALUE - b
        }
    }

Implementation language is Java, though of course this is more of a language-agnostic problem.

I was thinking if there's some logic we can employ to decide if a * b fits the range of an integer without casting it to a wider data type?

Solution ! based on Strelok's comment:

public static boolean CanTimes(int a, int b) {
    if (a == 0 || b == 0) {
        return true;
    }
    if (a > 0) {
        if (b > 0) {
            return a <= Integer.MAX_VALUE / b;
        } else {
            return a <= Integer.MIN_VALUE / b;
        }
    } else {
        if (b > 0) {
            return b <= Integer.MIN_VALUE / a;
        } else {
            return a <= -Integer.MAX_VALUE / b;
        }
    }
}

Answer 1

You can do the multiplication and then check whether dividing by one factor still gives the other.

EDIT

The above doesn't work all the time, as Dietrich Epp points out; it fails for -1 and Integer.MIN_VALUE. I don't know if there are any other edge cases. If not, then it would be easy to check for this one case.

Answer 2

As per my comment, here is the adapted version, with some unit tests:

public static int mulAndCheck( int a, int b )
{
    int ret;
    String msg = "overflow: multiply";
    if ( a > b )
    {
        // use symmetry to reduce boundry cases
        ret = mulAndCheck( b, a );
    }
    else
    {
        if ( a < 0 )
        {
            if ( b < 0 )
            {
                // check for positive overflow with negative a, negative b
                if ( a >= Integer.MAX_VALUE / b )
                {
                    ret = a * b;
                }
                else
                {
                    throw new ArithmeticException( msg );
                }
            }
            else if ( b > 0 )
            {
                // check for negative overflow with negative a, positive b
                if ( Integer.MIN_VALUE / b <= a )
                {
                    ret = a * b;
                }
                else
                {
                    throw new ArithmeticException( msg );

                }
            }
            else
            {
                // assert b == 0
                ret = 0;
            }
        }
        else if ( a > 0 )
        {
            // assert a > 0
            // assert b > 0

            // check for positive overflow with positive a, positive b
            if ( a <= Integer.MAX_VALUE / b )
            {
                ret = a * b;
            }
            else
            {
                throw new ArithmeticException( msg );
            }
        }
        else
        {
            // assert a == 0
            ret = 0;
        }
    }
    return ret;
}

@Test( expected = ArithmeticException.class )
public void testOverflow()
{
    mulAndCheck( Integer.MAX_VALUE, Integer.MAX_VALUE );
}

@Test( expected = ArithmeticException.class )
public void testOverflow1()
{
    mulAndCheck( Integer.MIN_VALUE, Integer.MAX_VALUE );
}

@Test
public void testTimesMinus1()
{
    Assert.assertEquals( Integer.MIN_VALUE + 1, mulAndCheck( Integer.MAX_VALUE, -1 ) );
    Assert.assertEquals( Integer.MAX_VALUE, mulAndCheck( Integer.MIN_VALUE + 1, -1 ) );
}

Answer 3

Since the multiplication of a*b is the same as a+a+a+... repeated b times (and vice-versa), you can do something like this:

(I renamed your CanMultiple() function to isIntMultiplication(), since I think its more clear )

public boolean isIntMultiplication(int a, int b) {
    // signs are not important in this context
    a = Math.abs(a);
    b = Math.abs(b);
    // optimization: I want to calculate a*b as the sum of a by itself repeated b times, so make sure b is the smaller one
    // i.e., 100*2 is calculated as 100+100 which is faster than summing 2+2+2+... a hundred times
    if (b > a) { int swap = a; a = b; b = swap; }

    int n = 0, total = a;
    while(++n < b) {
        if (total <= Integer.MAX_VALUE - a) {
            total += a;
        } else {
            return false;
        }
    }
    return true;
}

You see it in action:

// returns true, Integer.MAX_VALUE * 1 is still an int    
isIntMultiplication(Integer.MAX_VALUE, 1);

// returns false, Integer.MAX_VALUE * 2 is a long    
isIntMultiplication(Integer.MAX_VALUE, 2);

// returns true, Integer.MAX_VALUE/2 * 2 is still an int
isIntMultiplication(Integer.MAX_VALUE/2, 2);

// returns false, Integer.MAX_VALUE * Integer.MAX_VALUE is a long
isIntMultiplication(Integer.MAX_VALUE, Integer.MAX_VALUE);

This solution does not use long types, as required.

Answer 4

Mathematically, the sum of the log-base-2 should be less than 2³². Unfortunately, Math doesn't give us log base 2, but this is still simple enough:

static boolean canMultiply(int a, int b) {
    return Math.log(Math.abs(a)) + Math.log(Math.abs(b)) <= Math.log(Integer.MAX_VALUE);
}

EDITED: Due to (fair) flak, how about this simple approach that addresses OP's question exactly?

static boolean canMultiply(int a, int b) {
    return a == 0 || ((a * b) / a) == b;
}

If there's an overflow, dividing by the original number won't bring us back to starting number.
Importantly, this will work for longs, which can't be cast up.