정수의 거듭 제곱 계산

정수의 거듭 제곱 계산

---

Java에서 정수의 거듭 제곱을 계산하는 다른 방법이 있습니까?

나는 Math.pow(a, b)지금 사용 하지만을 반환하고 double일반적으로 많은 작업이 필요하며 ints 를 사용하고 싶을 때 덜 깨끗해 표시 (그러면 거듭 제곱도 항상 int).

a**b처럼 파이썬 간단한 것이 있습니까?

---

정수는 32 비트입니다. 이는 최대 값이 2^31 -1입니다. 보시다시피, 아주 작은 숫자의 경우 더 이상 정수로 표현할 수없는 결과를 빠르게 얻을 수 있습니다. 그 이유 Math.pow용도 double.

임의의 정수를 원하면 . 그러나 물론 효율성이 떨어집니다.BigInteger.pow

---

가장 좋은 알고리즘은 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

}

작업 실행 시간은 O (logb)입니다. 참조 : 추가 정보

---

아니오, 짧은 것은 없습니다 a**b

복식을 피하려는 다음은 간단한 루프입니다.

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

pow결과를 정수로 사용 하고 변환 예측 다음과 같이 결과를 캐스트하십시오.

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

---

2의 거듭 제곱 일 때 간단하고 빠른 시프트 표현을 사용할 수 있습니다. 1 << exponent

예 :

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

더 큰 지수 (31 이상)의 경우 대신 long 사용

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

btw. 코 틀린에, 당신은 shl대신에 <<이렇게

(자바) 1L << 32= 1L shl 32(kotlin)

---

Google Guava에는 정수용 수학 유틸리티가 있습니다. IntMath

---

Math.pow(a,b)에 사용한 것처럼 이전 간단히 사용 하고 이전에 사용하여 값을 CHAPTER 2 할 (int)수 있습니다. 아래는 이에 대한 예제로 사용할 수 있습니다.

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

여기서 a및 b수 double또는 int당신이 원하는대로 값. 이것은 정수 출력을 필요에 따라 값으로 변환합니다.

---

Guava의 수학 라이브러리는 정확한 정수 거듭 제곱을 계산할 때 유용한 두 가지 방법을 제공합니다.

pow(int b, int k) b의 k 번째 제곱을 계산하고 오버플로를 래핑합니다.

checkedPow(int b, int k)ArithmeticException오버플로 가 발생한다는 점을 제외하면 동일 합니다.

개인적으로 checkedPow()정수 지수화에 대한 대부분의 요구 사항을 듣고 이중 버전 및 반올림 등을 사용하는 것보다 더 깨끗하고 깔끔합니다. 거듭 함수 제곱을 원하는 거의 모든 곳에서 오버플로는 오류입니다 (또는 불가능할 수 없습니다.).

long결과를 얻으려면 해당 메소드 를 사용하고 인수를 받을 수 있습니다 .LongMathint

---

나는 수정 (경계, 심지어 확인, 음수 확인) Qx__ 답변을 관리했습니다. 자신의 책임하에 사용하십시오. 0 ^ -1, 0 ^ -2 등 .. 0을 반환합니다.

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

---

파워 계산을위한 반복 제곱 알고리즘에 대한 간단한 (오버플로 또는 인수 유효성 검사 없음) 구현 :

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

시간 복잡도는 지수 p에 대한 로그입니다 (즉, p를 필요한 비트 수에 선형).

---

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

}

---

Python (a ** b로 거듭 제곱을 계산할 수있는 곳)과 달리 JAVA에는 두 숫자의 거듭 제곱 결과를 달성하는 지름길 방법이 없습니다. Java는 Math 클래스에 pow라는 함수가 있으며 Double 값을 반환합니다.

double pow(double base, double exponent)

그러나 동일한 함수를 사용하여 정수의 거듭 제곱을 계산할 수도 있습니다. 다음 프로그램에서 동일한 작업을 수행하고 마지막으로 결과를 정수 (타입 캐스팅)로 변환합니다. 예를 따르십시오.

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

또는 The java.math.BigInteger.pow(int exponent)는 값이 (this ^ exponent) 인 BigInteger를 반환합니다. 지수는 BigInteger가 아닌 정수입니다. 예:

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

---

아래 논리를 사용하여 a의 n 거듭 제곱을 계산합니다.

일반적으로 a의 n 거듭 제곱을 계산하려면. 우리는 'a'에 n 번을 곱할 것입니다.이 접근법의 시간 복잡도는 O (n) n 제곱을 2로 나누고 지수를 계산 = n / 2까지만 'a'를 곱합니다. 가치를 두 배로 늘리십시오. 이제 시간 복잡도가 O (n / 2)로 줄어 듭니다.

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는 전력을 공급하려는 숫자이고, n은 거듭 제곱이고, n이 0이면 1을 반환하고, n이 1이면 기본을 반환하고, 조건이 충족되지 않으면 base * (powerN) 공식을 사용합니다. (base, n-1)) 예 :이 공식을 사용하여 2를 올린 값은 2 (base) * 2 (powerN (base, n-1))입니다.

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

참조 URL : https://stackoverflow.com/questions/8071363/calculating-powers-of-integers