Czy istnieje algorytm określający, czy a * b mieści się w możliwych wartościach liczby całkowitej? (bez rzutowania na szerszy typ)

Question

Witam wszystkich zastanawiałem się, czy istnieje sposób wdrożenia tej metody bez przesyłania do szerszego typu danych (np. długi, podwójny itp.)?

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

Na przykład moglibyśmy wdrożyć jedną dla metody CanAdd (bez poświaty) jako takie:

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

język Wdrożenie jest Java, choć oczywiście jest to większym problemem językowym-agnostykiem.

Zastanawiam się, czy istnieje jakaś logika, którą możemy zastosować, aby zdecydować, czy a * b mieści się w zakresie liczby całkowitej bez rzucania go do szerszego typu danych?

Rozwiązanie! na podstawie komentarza zStrelok:

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

Jak na mój komentarz, tutaj jest wersja przystosowana, z niektórych testów jednostkowych:

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 2

Można wykonać mnożenie, a następnie sprawdzić, czy podzielenie przez jednego czynnika nadal daje drugą.

EDIT

Powyższe nie działa cały czas, jak Dietrich Epp zaznacza; nie powiedzie się dla -1 i Integer.MIN_VALUE. Nie wiem, czy są jakieś inne przypadki krańcowe. Jeśli nie, to łatwo byłoby sprawdzić tę jedną sprawę.

Answer 3

Matematycznie suma dziennika bazy-2 powinna być mniejsza niż 2 . Niestety, Math nie daje nam logarytm przy podstawie 2, ale to jest nadal dość proste:

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

edycja: Ze względu na (fair) flak, jak o tym prostym podejściu, która dotyczy dokładnie pytanie OP?

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

Jeśli wystąpi przepełnienie, podzielenie przez pierwotny numer nie spowoduje powrotu do numeru początkowego.
Co ważne, zadziała to w przypadku longs, której nie można odrzucić .

Answer 4

Ponieważ mnożenie a*b jest taka sama jak a+a+a+... powtarzane b razy (i vice versa), można zrobić coś takiego:

(I zmieniono nazwę funkcji CanMultiple() do isIntMultiplication(), ponieważ myślę, że to bardziej jasne)

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

zobaczyć go w akcji:

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

To rozwiązanie nie wymaga użycia typów long.