Berechnung der Potenzen von ganzen Zahlen

Gibt es in Java eine andere Möglichkeit, die Potenz einer Ganzzahl zu berechnen?

Ich benutze Math.pow(a, b)jetzt, aber es gibt a zurück double, und das ist normalerweise viel Arbeit und sieht weniger sauber aus, wenn Sie nur ints verwenden möchten (eine Leistung führt dann auch immer zu einem int).

Gibt es etwas so Einfaches a**bwie in Python?

Ganzzahlen sind nur 32 Bit. Dies bedeutet, dass sein Maximalwert ist 2^31 -1. Wie Sie sehen, haben Sie bei sehr kleinen Zahlen schnell ein Ergebnis, das nicht mehr durch eine Ganzzahl dargestellt werden kann. Deshalb Math.powverwendet double.

Wenn Sie eine beliebige Ganzzahlgenauigkeit wünschen, verwenden Sie BigInteger.pow. Aber es ist natürlich weniger effizient.

Am besten basiert der Algorithmus auf der rekursiven Potenzdefinition von a ^ b.

long pow (long a, int b)
{
    if ( b == 0)        return 1;
    if ( b == 1)        return a;
    if (isEven( b ))    return     pow ( a * a, b/2); //even a=(a^2)^b/2
    else                return a * pow ( a * a, b/2); //odd  a=a*(a^2)^b/2

}

Die Laufzeit der Operation ist O (logb). Referenz: Weitere Informationen

Nein, es gibt nicht so kurz wie a**b

Hier ist eine einfache Schleife, wenn Sie Doppel vermeiden möchten:

long result = 1;
for (int i = 1; i <= b; i++) {
   result *= a;
}

Wenn Sie powdas Ergebnis verwenden und in eine Ganzzahl konvertieren möchten, wandeln Sie das Ergebnis wie folgt um:

int result = (int)Math.pow(a, b);

Wenn es die Potenz von 2 ist. Denken Sie daran, dass Sie einen einfachen und schnellen Shift-Ausdruck verwenden können 1 << exponent

Beispiel:

2 ² = 1 << 2= (int) Math.pow(2, 2)
2 ¹⁰ = 1 << 10=(int) Math.pow(2, 10)

Verwenden Sie für größere Exponenten (über 31) stattdessen long

2 ³² = 1L << 32=(long) Math.pow(2, 32)

Übrigens. in Kotlin haben Sie shlstattdessen <<so

(Java) 1L << 32= 1L shl 32(Kotlin)

Google Guava verfügt über mathematische Dienstprogramme für Ganzzahlen. IntMath

Die Mathematikbibliotheken von Guava bieten zwei Methoden, die bei der Berechnung der exakten ganzzahligen Potenzen hilfreich sind:

pow(int b, int k) berechnet b bis zur k-ten Leistung und umschließt den Überlauf

checkedPow(int b, int k)ist identisch, außer dass es ArithmeticExceptionauf Überlauf wirft

checkedPow()Erfüllt persönlich die meisten meiner Anforderungen an die Potenzierung von Ganzzahlen und ist sauberer und sicherer als die Verwendung von Doppelversionen und Rundungen usw. An fast allen Stellen, an denen ich eine Potenzfunktion möchte, ist ein Überlauf ein Fehler (oder unmöglich, aber ich möchte wissen, ob das Unmögliche wird jemals möglich).

Wenn Sie ein longErgebnis erhalten möchten , können Sie einfach die entsprechenden LongMathMethoden verwenden und intArgumente übergeben.

Nun, Sie können einfach Math.pow(a,b)wie zuvor verwenden und den Wert einfach konvertieren, indem Sie ihn (int)vorher verwenden. Das Folgende könnte als Beispiel dafür dienen.

int x = (int) Math.pow(a,b);

wo aund bkönnte sein doubleoder intWerte wie Sie wollen. Dadurch wird die Ausgabe einfach nach Bedarf in einen ganzzahligen Wert konvertiert.

import java.util.*;

public class Power {

    public static void main(String args[])
    {
        Scanner sc=new Scanner(System.in);
        int num = 0;
        int pow = 0;
        int power = 0;

        System.out.print("Enter number: ");
        num = sc.nextInt();

        System.out.print("Enter power: ");
        pow = sc.nextInt();

        System.out.print(power(num,pow));
    }

    public static int power(int a, int b)
    {
        int power = 1;

        for(int c = 0; c < b; c++)
            power *= a;

        return power;
    }

}

Ich habe es geschafft, die Qx__-Antwort zu ändern (Grenzen, sogar prüfen, negative Zahlen prüfen). Benutzung auf eigene Gefahr. 0 ^ -1, 0 ^ -2 etc .. gibt 0 zurück.

private static int pow(int x, int n) {
        if (n == 0)
            return 1;
        if (n == 1)
            return x;
        if (n < 0) { // always 1^xx = 1 && 2^-1 (=0.5 --> ~ 1 )
            if (x == 1 || (x == 2 && n == -1))
                return 1;
            else
                return 0;
        }
        if ((n & 1) == 0) { //is even 
            long num = pow(x * x, n / 2);
            if (num > Integer.MAX_VALUE) //check bounds
                return Integer.MAX_VALUE; 
            return (int) num;
        } else {
            long num = x * pow(x * x, n / 2);
            if (num > Integer.MAX_VALUE) //check bounds
                return Integer.MAX_VALUE;
            return (int) num;
        }
    }

Eine einfache Implementierung (keine Überprüfung auf Überlauf oder auf Gültigkeit von Argumenten) für den Algorithmus für wiederholtes Quadrieren zur Berechnung der Leistung:

/** Compute a**p, assume result fits in a 32-bit signed integer */ 
int pow(int a, int p)
{
    int res = 1;
    int i1 = 31 - Integer.numberOfLeadingZeros(p); // highest bit index
    for (int i = i1; i >= 0; --i) {
        res *= res;
        if ((p & (1<<i)) > 0)
            res *= a;
    }
    return res;
}

Die zeitliche Komplexität ist logarithmisch zum Exponenten p (dh linear zu der Anzahl von Bits, die zur Darstellung von p erforderlich sind).

Es gibt einige Probleme mit der Pow-Methode:

1. Wir können (y & 1) ersetzen == 0; mit y% 2 == 0 sind
   bitweise Operationen immer schneller.

Ihr Code dekrementiert immer y und führt eine zusätzliche Multiplikation durch, einschließlich der Fälle, in denen y gerade ist. Es ist besser, diesen Teil in die else-Klausel aufzunehmen.

public static long pow(long x, int y) {
        long result = 1;
        while (y > 0) {
            if ((y & 1) == 0) {
                x *= x;
                y >>>= 1;
            } else {
                result *= x;
                y--;
            }
        }
        return result;
    }

Im Gegensatz zu Python (wo Potenzen durch a ** b berechnet werden können) hat JAVA keine solche Abkürzung, um das Ergebnis der Potenz zweier Zahlen zu erzielen. Java hat eine Funktion namens pow in der Math-Klasse, die einen Double-Wert zurückgibt

double pow(double base, double exponent)

Mit derselben Funktion können Sie aber auch Potenzen von Ganzzahlen berechnen. Im folgenden Programm habe ich dasselbe getan und schließlich konvertiere ich das Ergebnis in eine Ganzzahl (Typumwandlung). Folge dem Beispiel:

import java.util.*;
import java.lang.*; // CONTAINS THE Math library
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n= sc.nextInt(); // Accept integer n
        int m = sc.nextInt(); // Accept integer m
        int ans = (int) Math.pow(n,m); // Calculates n ^ m
        System.out.println(ans); // prints answers
    }
}

Alternativ gibt The java.math.BigInteger.pow(int exponent)eine BigInteger zurück, deren Wert (this ^ exponent) ist. Der Exponent ist eher eine Ganzzahl als eine BigInteger. Beispiel:

import java.math.*;
public class BigIntegerDemo {
public static void main(String[] args) {
      BigInteger bi1, bi2; // create 2 BigInteger objects          
      int exponent = 2; // create and assign value to exponent
      // assign value to bi1
      bi1 = new BigInteger("6");
      // perform pow operation on bi1 using exponent
      bi2 = bi1.pow(exponent);
      String str = "Result is " + bi1 + "^" +exponent+ " = " +bi2;
      // print bi2 value
      System.out.println( str );
   }
}

Verwenden Sie die folgende Logik, um die n-Potenz von a zu berechnen.

Normalerweise, wenn wir n Potenzen von a berechnen wollen. Wir werden 'a' mit n multiplizieren. Die zeitliche Komplexität dieses Ansatzes wird O (n) sein. Teilen Sie die Potenz n mit 2, berechnen Sie Exponentattion = multiplizieren Sie 'a' nur mit n / 2. Verdoppeln Sie den Wert. Jetzt wird die Zeitkomplexität auf O (n / 2) reduziert.

public  int calculatePower1(int a, int b) {
    if (b == 0) {
        return 1;
    }

    int val = (b % 2 == 0) ? (b / 2) : (b - 1) / 2;

    int temp = 1;
    for (int i = 1; i <= val; i++) {
        temp *= a;
    }

    if (b % 2 == 0) {
        return temp * temp;
    } else {
        return a * temp * temp;
    }
}

base ist die Zahl, die Sie einschalten möchten, n ist die Leistung, wir geben 1 zurück, wenn n 0 ist, und wir geben die Basis zurück, wenn n 1 ist. Wenn die Bedingungen nicht erfüllt sind, verwenden wir die Formel base * (powerN) (Basis, n-1)) zB: 2 zur Verwendung dieser Formel angehoben ist: 2 (Basis) * 2 (PotenzN (Basis, n-1)).

public int power(int base, int n){
   return n == 0 ? 1 : (n == 1 ? base : base*(power(base,n-1)));
}

Apache hat ArithmeticUtils.pow(int k, int e).

import java.util.Scanner;

class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();

        for (int i = 0; i < t; i++) {

            try {
                long x = sc.nextLong();
                System.out.println(x + " can be fitted in:");
                if (x >= -128 && x <= 127) {
                    System.out.println("* byte");
                }
                if (x >= -32768 && x <= 32767) {
                    //Complete the code
                    System.out.println("* short");
                    System.out.println("* int");
                    System.out.println("* long");
                } else if (x >= -Math.pow(2, 31) && x <= Math.pow(2, 31) - 1) {
                    System.out.println("* int");
                    System.out.println("* long");
                } else {
                    System.out.println("* long");
                }
            } catch (Exception e) {
                System.out.println(sc.next() + " can't be fitted anywhere.");
            }

        }
    }
}