Compruebe si un entero es una potencia entera de otro

Question

Esto es un interview question: "Dado 2 enteros xey, verifique si x es una potencia entera de y" (por ejemplo, para x = 8 yy = 2 la respuesta es " verdadero ", y para x = 10 ey = 2" falso ").

La solución obvia es:

int n = y; while(n < x) n *= y; return n == x

Ahora estoy pensando en cómo mejorarlo.

Por supuesto, puedo verificar algunos casos especiales: p. ambos x y y deben ser números pares o impares, es decir, podemos verificar el bit menos significativo de x y y. Sin embargo, me pregunto si puedo mejorar el algoritmo central en sí mismo.

Answer 1

Haría mejor en dividir y en x. La primera vez que obtienes un resto distinto de cero sabes que x no es una potencia entera de y.

while (x%y == 0) x = x/y 
return x == 1 

Esto se ocupa de su punto par/impar en la primera iteración.

Answer 2

Significa registro _y (x) debería ser un número entero . No necesita ningún bucle. en O (1) tiempo

public class PowerTest { 

    public static boolean isPower(int x, int y) { 
     double d = Math.log(Math.abs(x))/Math.log(Math.abs(y)); 

     if ((x > 0 && y > 0) || (x < 0 && y < 0)) { 
      if (d == (int) d) { 
       return true; 
      } else { 
       return false; 
      } 
     } else if (x > 0 && y < 0) { 
      if ((int) d % 2 == 0) { 
       return true; 
      } else { 
       return false; 
      } 
     } else { 
      return false; 
     } 
    } 

    /** 
    * @param args 
    */ 
    public static void main(String[] args) { 

     System.out.println(isPower(-32, -2)); 
     System.out.println(isPower(2, 8)); 
     System.out.println(isPower(8, 12)); 
     System.out.println(isPower(9, 9)); 
     System.out.println(isPower(-16, 2)); 
     System.out.println(isPower(-8, -2)); 
     System.out.println(isPower(16, -2)); 
     System.out.println(isPower(8, -2)); 
    } 

} 

Answer 3

Me implementar la función de este modo:

bool IsWholeNumberPower(int x, int y) 
{ 
    double power = log(x)/log(y); 
    return floor(power) == power; 
} 

Esto no debería necesitar cheque dentro de un delta como es común con comparaciones en coma flotante, ya que' revisando números enteros.

Answer 4

Pensándolo bien, no hagas esto. No funciona para x negativo y/o y. Tenga en cuenta que todas las demás respuestas basadas en log que se presentan en este momento también se han roto exactamente de la misma manera.

La siguiente es una solución general rápida (en Java):

static boolean isPow(int x, int y) { 
    int logyx = (int)(Math.log(x)/Math.log(y)); 
    return pow(y, logyx) == x || pow(y, logyx + 1) == x; 
} 

Dónde pow() es una función de número entero exponenciación como la siguiente en Java:

static int pow(int a, int b) { 
    return (int)Math.pow(a, b); 
} 

(Esto funciona debido a la siguiente garantía provista por Math.pow: "Si ambos argumentos son enteros, entonces el resultado es exactamente igual al resultado matemático de elevar el primer argumento a la potencia del segundo argumento ... ")

La razón para ir con logaritmos en lugar de división repetida es el rendimiento: mientras que log is slower than division, es más lento por un pequeño múltiplo fijo. Al mismo tiempo, elimina la necesidad de un bucle y, por lo tanto, le proporciona un algoritmo de tiempo constante.

Answer 5

Esto se ve para el exponente en O (log N) pasos:

#define MAX_POWERS 100 

int is_power(unsigned long x, unsigned long y) { 
    int i; 
    unsigned long powers[MAX_POWERS]; 
    unsigned long last; 
    last = powers[0] = y; 

    for (i = 1; last < x; i++) { 
    last *= last; // note that last * last can overflow here! 
    powers[i] = last; 
    } 
    while (x >= y) { 
    unsigned long top = powers[--i]; 
    if (x >= top) { 
     unsigned long x1 = x/top; 
     if (x1 * top != x) return 0; 
     x = x1; 
    } 
    } 
    return (x == 1); 
} 

Los números negativos no son manejados por este código, pero se puede hacer facilmente con un poco de código condicional cuando i = 1

Answer 6

En los casos en que y es 2, hay un enfoque rápido que evita la necesidad de un bucle. Este enfoque puede extenderse a los casos en y es un poder mayor de 2.

Si x es una potencia de 2, la representación binaria de x tiene un único conjunto de bits. Existe un algoritmo bastante simple para el conteo de bits para contar los bits en un entero en el tiempo O (log n) donde n es el ancho de bits de un entero. Muchos procesadores también tienen instrucciones especializadas que pueden manejar esto como una operación única, aproximadamente tan rápido como (por ejemplo) una negación entera.

Sin embargo, para extender el enfoque, primero tome un enfoque ligeramente diferente para verificar un solo bit. Primero determine la posición del bit menos significativo. De nuevo, existe un algoritmo simple de manipulación de bits, y muchos procesadores tienen instrucciones especializadas rápidas.

Si este bit es el único, entonces (1 << pos) == x. La ventaja aquí es que si está probando una potencia de 4, puede probar pos % 2 == 0 (el bit único está en una posición pareja). Si prueba una potencia de cualquier potencia de dos, puede realizar la prueba para pos % (y >> 1) == 0.

En principio, podría hacer algo similar para probar potencias de 3 y potencias de potencias de 3. El problema es que necesitaría una máquina que funcione en la base 3, lo cual es un poco improbable. Sin duda puede probar cualquier valor x para ver si su representación en la base y tiene un solo dígito distinto de cero, pero estaría haciendo más trabajo que ya está haciendo. Lo anterior explota el hecho de que las computadoras funcionan en binario.

Probablemente no vale la pena hacerlo en el mundo real, sin embargo.

Answer 7

Esto parece ser bastante rápido para números positivos ya que encuentra los límites inferior y superior de la potencia deseada y luego aplica la búsqueda binaria.

#include <iostream> 
#include <cmath> 
using namespace std; 

//x is the dividend, y the divisor. 
bool isIntegerPower(int x, int y) 
{ 
    int low = 0, high; 
    int exp = 1; 
    int val = y; 
    //Loop by changing exponent in the powers of 2 and 
    //Find out low and high exponents between which the required exponent lies. 
    while(1) 
    { 
     val = pow((double)y, exp); 
     if(val == x) 
      return true; 
     else if(val > x) 
      break; 
     low = exp; 
     exp = exp * 2; 
     high = exp; 
    } 
    //Use binary search to find out the actual integer exponent if exists 
    //Otherwise, return false as no integer power. 
    int mid = (low + high)/2; 
    while(low < high) 
    { 
     val = pow((double)y, mid); 
     if(val > x) 
     { 
      high = mid-1; 
     } 
     else if(val == x) 
     { 
      return true; 
     } 
     else if(val < x) 
     { 
      low = mid+1; 
     } 
     mid = (low + high)/2; 
    } 
    return false; 
} 

int main() 
{ 
    cout<<isIntegerPower(1024,2); 
} 

Answer 8

Las respuestas anteriores son correctas, la respuesta de Paul me ha gustado mejor. Es simple y limpio. Aquí es la implementación en Java de lo que sugirió:

public static boolean isPowerOfaNumber(int baseOrg, int powerOrg) { 
    double base = baseOrg; 
    double power = powerOrg; 

    while (base % power == 0) 
     base = base/power; 
    // return true if base is equal 1 
    return base == 1; 
} 

Answer 9

double a=8; 
    double b=64; 

    double n = Math.log(b)/Math.log(a); 
    double e = Math.ceil(n); 

    if((n/e) == 1){ 
     System.out.println("true"); 
    } else{ 
     System.out.println("false"); 
    } 

Answer 10

Si usted tiene acceso a la mayor potencia de y, que puede ser instalado dentro del tipo de datos requerido, esta es una manera muy resbaladizo de resolver este problema.

Digamos, para nuestro caso, y == 3. Entonces, necesitaríamos comprobar si x es una potencia de 3.

Dado que necesitamos verificar si un número entero x es una potencia de 3, comencemos a pensar sobre este problema en términos de qué información ya está en mano.

1162261467 es la mayor potencia de 3 que puede caber en una int Java.
1162261467 = 3^19 + 0

La x indicada se puede expresar como [(a power of 3) + (some n)]. Creo que es bastante elemental poder probar que si n es 0 (que ocurre iff x es una potencia de 3), 1162261467 % x = 0.

Por lo tanto, para verificar si un número entero dado x es una potencia de tres, verifique si x > 0 && 1162261467 % x == 0.

Generalización. Para verificar si un entero dado x es una potencia de un entero dado y, verifique si x > 0 && Y % x == 0: Y es la mayor potencia de y que puede caber en un tipo de datos entero.

La idea general es que si A es alguna potencia de Y, A puede expresarse como B/Ya, donde a es un entero y A < B. Sigue el mismo principio exacto para A > B. El caso A = B es elemental.

Answer 11

me encontró esta solución: // Compruebe si A puede ser expresado como potencia de dos números enteros

int isPower(int A) 
    { 
    int i,a; 
    double p; 
    if(A==1) 
    return 1; 
    for(int a=1; a<=sqrt(A);++a) 
    { 
     p=log(A)/log(a); 
     if(p-int(p)<0.000000001) 
     return 1; 
    } 
    return 0; 
    } 

binarycoder.org

Answer 12

Aquí es una versión de Python, que reúne las ideas de @salva y @ Axn y se modifica para que no genere ningún número mayor que los dados y utiliza solo el almacenamiento simple (leer, "sin listas") reduciendo repetidamente el número de interés:

def perfect_base(b, n): 
    """Returns True if integer n can be expressed as b**e where 
    n is a positive integer, else False.""" 

    assert b > 1 and n >= b and int(n) == n and int(b) == b 

    # parity check 
    if not b % 2: 
     if n % 2: 
      return False # b,n is even,odd 
     if b == 2: 
      return n & (n - 1) == 0 
     if not b & (b - 1) and n & (n - 1): 
      return False # b == 2**m but n != 2**M 
    elif not n % 2: 
     return False # b,n is odd,even 

    while n >= b: 
     d = b 
     while d <= n: 
      n, r = divmod(n, d) 
      if r: 
       return False 
      d *= d 
    return n == 1