Ich muss Methode schreiben, die nur ganze Zahlen

Question

zurück

Ich muss eine Methode in Java schreiben, um die Leistung nur Integer-Zahl zurückzugeben, und ich möchte diese Methode -1 oder Ausnahme auslösen, wenn die Zahl die Ganzzahl überschreitet. MAX_VALUE:

habe ich versucht, den ersten und einfachen Schritt:

public static int GetPower(int base, int power) 
{ 
    int result = 1; 

    for(int i = 1; i<=power; i++) 
    { 
     result *= base; 
     if (result < 0) { 
      break; // not very acurate 
     } 
    } 
    if (result < 0) { 
     return -1; 
    } 
    return result; 
} 

Ist das oben beschriebene Verfahren genau, wie nach dem Debuggen ich das gefunden, wenn das Ergebnis der Integer.MAX_VALUE übersteigt es negative Zahl gehen, oder es ist eine andere Möglichkeit, damit umzugehen?

Answer 1

Ihre Methode funktioniert, wenn die Basis nur eine positive ganze Zahl sein kann. Unterlauf kann vorkommen, dass Ihre Basis eine negative ganze Zahl ist und Ihre Potenz eine ungerade Zahl ist.

Eine einfache, aber nicht optimale Möglichkeit, diese Situation zu behandeln, ist die Verwendung eines langen Datentyps zum Speichern der Ausgabe und Vergleichen der Ausgabe, um zu überprüfen, ob sie zwischen Integer.MAX_VALUE und Integer.MIN_VALUE liegt.

Answer 2

Sie überprüfen, ist falsch. Versuchen Sie Ihre Methode mit 1 < < 32 und 2 als Parameter.

Korrekte Überprüfung wird in etwa so sein result==result*base/base Wenn es wahr ist, können Sie result und base ohne Überlauf multiplizieren.

Answer 3

Der von Ihnen bemerkte Effekt ist ein numerischer Überlauf. Wenn Sie eins zu Integer.MAX_VALUE hinzufügen, erhalten Sie Integer.MIN_VALUE als Ergebnis.

Jetzt, was Sie brauchen, ist mehr Platz, um Ihren Wert zu speichern. Da Sie innerhalb des 32-Bit-Integer-Bereichs arbeiten möchten, brauchen Sie das nächstgrößere Ding. Und das wäre ein 64-Bit Wert. Dies ist in jedem Fall schneller im Vergleich zu allen BigDecimals Verwendung.

Sie müssen nur in einem beliebigen Schleifenschritt prüfen, wenn Ihr Wert Integer.MAX_VALUE überschritten hat, und abbrechen, wenn das passiert.

So würde der resultierende Code so etwas wie diese:

public static int GetPower(int base, int power) 
{ 
    long result = 1; 

    for(int i = 1; i <= power; i++) 
    { 
     result *= base; 
     if (result > Integer.MAX_VALUE) { 
      return -1; 
     } 
    } 
    return result; 
} 

Außerdem empfehle ich Ihnen die Eingabe der Funktion bestätigen, dass die Basis, um sicherzustellen, ist nicht negativ.

Answer 4

Die Antworten von Nitram und PythaLye funktionieren, aber ich mag die Idee nicht, einen anderen Datentyp zu verwenden, um Grenzen zu überprüfen. Stattdessen würde ich vorschlagen, dass Sie diese einfache Prüfung verwenden:

// This basically means result * base > boundary 
if ((base > 0 && result > (Integer.MAX_VALUE/base)) 
    || (base < 0 && result < (Integer.MIN_VALUE/-base)) // Negative base case 
{ 
    return -1; 
} 

So würde der Code:

public static int GetPower(int base, int power) 
{ 
    int result = 1; 

    for(int i = 1; i<=power; i++) 
    { 
     if ((base > 0 && result > (Integer.MAX_VALUE/base)) 
      || (base < 0 && result < (Integer.MIN_VALUE/-base)) { 
      return -1; 
     } 

     result *= base; 
    } 

    return result; 
} 

Answer 5

Wie Sie einfache Implementierung der Methode pow haben, die keine negativen Zahlen oder Werte nicht akzeptiert, Mein Vorschlag ist es, den höchsten erlaubten Wert zu erstellen und zu überprüfen, ob das Ergebnis kleiner ist.

public static int getPower(int base, int power) 
    { 
     int result = 1; 
     int maxAllowed = Integer.MAX_VALUE/base; 

     for(int i = 1; i<=power; i++) 
     { 
      result *= base; 
      if (i!=power && result>=maxAllowed){ 
       return -1; 
      } 

     } 

     return result; 
    } 

Aber im Allgemeinen, ich weiß nicht neu zu erfinden Rad wird dringend empfohlen, und

Answer 6

Es gibt bereits eine perfekt tragfähige Potenzfunktion in java.lang.Math mit Math.pow Methode.Ich schlage vor, es für die Randfälle zu verwenden.

public class GetPower { 

    public static int getPower(int base, int power) { 
     double result = Math.pow(base, power); 
     // check result in range 
     if (result > Integer.MAX_VALUE) 
      return -1; 
     if (result < Integer.MIN_VALUE) 
      return -1; 
     return (int) result; 
    } 

    public static void main(String[] args) { 
     for (int base=0; base<=10; ++base) { 
      for (int power=0; power<=10; ++power) { 
       int result = getPower(base, power); 
       System.out.println("getPower(" + base + ", " + power + ") = " + result); 
      } 
     } 
    } 

} 

Es gibt keine Notwendigkeit, das Rad neu zu erfinden. Sie müssen sich keine Gedanken über Gleitkomma-Ungenauigkeiten machen - alle int-Werte sind perfekt als doppelte Werte darstellbar.

Answer 7

Wie bereits erwähnt, ermöglicht die Verwendung eines "größeren" Datentyps die Validierung und einfache Berechnung - aber was ist, wenn kein größerer Datentyp ist?

Sie Test mathematisch kann, wenn es zu einem Überlauf führen würde:

Wenn Sie base^power sind caluclating, bedeutet, dass base^power = result - es bedeutet auch power-th square of result = base - das maximale Ergebnis ist Integer.MAX_VALUE erlaubt - sonst Sie einen Überlauf haben.

Die power-th root einer beliebigen Anzahl größer als Null wird IMMER innerhalb des Bereichs liegen ]0,number] - keine Chance Arithmetik überläuft.

Also - wir vergleichen die base Sie mit dem power-th root von Integer.MAX_VALUE verwenden - ist base GRÖSSER? Dann werden Sie einen Überlauf auftreten - sonst würde es bleiben unten (oder gleich zu) das Ergebnis der Integer.MAX_VALUE

private static double powSafe(double base, int pow){ 
    //this is the p-th root of the maximum integer allowed 
    double root = Math.pow(Integer.MAX_VALUE, 1.0/pow); 

    if (root < base){ 
     throw new ArithmeticException("The calculation of " + base + "^" + pow + " would overflow."); 
    }else{ 
     return Math.pow(base, pow); 
    } 
} 

public static void main(String[] argv) 
{ 
    double rootOfMaxInt = Math.pow(Integer.MAX_VALUE, 1.0/2); 
    try{ 
     //that should be INTEGER.MAX_VALUE, so valid. 
     double d1 = powSafe(rootOfMaxInt, 2); 
     System.out.println(rootOfMaxInt + "^2 = " + d1); 
    }catch (ArithmeticException e){ 
     System.out.println(e.getMessage()); 
    } 

    try{ 
     //this should overflow cause "+1" 
     double d2 = powSafe(rootOfMaxInt +1, 2); 
     System.out.println("("rootOfMaxInt + "+ 1)^2 = " + d1); 
    }catch (ArithmeticException e){ 
     System.out.println(e.getMessage()); 
    } 

    double the67thRootOfMaxInt = Math.pow(Integer.MAX_VALUE, 1.0/67); 
    try{ 
     //and so, it continues 
     double d3 = powSafe(the67thRootOfMaxInt, 67); 
     System.out.println(the67thRootOfMaxInt + "^67 = " + d3); 

     double d4 = powSafe(the67thRootOfMaxInt +1, 67); 
     System.out.println("(" + the67thRootOfMaxInt + " + 1)^67 = " + d3); 

    }catch (ArithmeticException e){ 
     System.out.println(e.getMessage()); 
    } 
} 

führt zu

46340.950001051984^2 = 2.147483647E9 
The calculation of 46341.950001051984^2 would overflow. 
1.3781057199632372^67 = 2.1474836470000062E9 
The calculation of 2.378105719963237^67 would overflow. 

Hinweis, dass es Unschärfen Ursache doppelt erscheinen nicht unendlich ist Präzision, die bereits den Ausdruck 2nd square of Integer.Max_Value abschneidet, weil Integer.Max_value ungerade ist.