Есть ли алгоритм для определения, подходит ли a * b к возможным значениям целого числа? (без приведения к более широкому типу)

Question

Привет, все, что мне было интересно, есть ли способ реализовать этот метод без приведения к более широкому типу данных (например, long, double и т. Д.)?

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

Например, мы могли бы реализовать один для метода CanAdd (без приведения) следующим образом:

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

Язык реализации - Java, хотя, конечно, это больше не зависит от языка.

Я думал, есть ли какая-то логика, которую мы можем использовать, чтобы решить, соответствует ли a * b диапазону целого числа, не приводя его к более широкому типу данных?

Решение! на основании комментария Стрелка:

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

Поскольку умножение a*b такое же, как a+a+a+... повторение b раз (и наоборот), вы можете сделать что-то вроде этого:

(я переименовал вашу функцию CanMultiple()до isIntMultiplication(), так как я думаю, что это более понятно)

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

Вы видите это в действии:

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

Это решение не использует long типы, как требуется.

Answer 2

Согласно моему комментарию, вот адаптированная версия с некоторыми юнит-тестами:

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

Вы можете выполнить умножение, а затем проверить, дает ли деление на один множитель другой.

EDIT

Вышеуказанное не работает постоянно, как указывает Дитрих Эпп; это терпит неудачу для -1 и Integer.MIN_VALUE. Я не знаю, есть ли другие крайние случаи. Если нет, то было бы легко проверить этот случай.

Answer 4

Математически сумма log-base-2 должна быть меньше 2 ³² .К сожалению, Math не дает нам базы данных 2, но это все еще достаточно просто:

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

РЕДАКТИРОВАНИЕ: Из-за (справедливой) проблемы, как насчет этого простого подхода, который обращается кВопрос ОП точно?

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

Если переполнение, деление на исходное число не вернет нас к начальному номеру.
Важно, что это будет работать для longs, что нельзя быть брошенным.