* 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のための1つを実現することができます。もちろん、これは言語に依存しない問題の詳細ですけれども

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のです。

私は、* bがより広いデータ型にキャストせずに整数の範囲に適合するかどうかを判断するために採用できるロジックがあると思っていましたか？

解決策！ Strelokさんのコメントに基づいて：

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

、ここに適応したバージョンは、いくつかのユニットテストで、次のとおりです。

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

あなたは乗算を行い、その後、一つの要因で割ることはまだ他を与えるかどうかを確認することができます。

EDIT

上記ディートリッヒエップが指摘するように、すべての時間を動作しません。 -1とInteger.MIN_VALUEに失敗します。他のエッジケースがあるかどうかはわかりません。そうでない場合は、この1つのケースを確認するのは簡単です。私のコメントを1として

Answer 3

数学的には、ログ・ベース-2の合計が2未満でなければなりません。残念ながら、数学はベース2を記録し、私たちを与えるものではありませんが、これはまだ十分に簡単です：

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

EDITED：により（公正）非難に、どのように正確にOPの質問に対処し、この単純なアプローチについてはどうですか？

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

オーバーフローがある場合は、元の数値で除算しても開始番号に戻りません。
重要：これはlongsで動作します。はキャストアップできません。

Answer 4

a*bの乗算はa+a+a+...がb回（またはその逆）を繰り返したとして、あなたはこのような何かを行うことができます同じですので：

私はそのをより明確だと思うので、（私は、isIntMultiplication()にごCanMultiple()機能と改名）

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タイプを使用しません。