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

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 ) );
}