Foro de elhacker.net

Hola a todos

en el colegio estoy haciendo numeros binarios y el profesor nos ha planteado una pregunta como ampliacion de la asignatura y por mas que busco no encuentro solucion, haber si alguno de vosotros me puede echar una mano jeje
ahi va

¿Hay algun truco para calcular potencias binarias?
por ejemplo (1001)^3

algun tipo de relacion o truquillo
que no sea pasarlo a numero deciamal xD

Bueno, en lo personal no se me ocurre una manera mas rapida de calcular a^b que no sea con exponenciación binaria.

Ej. 14 = 1110
a¹⁴ = a⁸ * a⁴ * a²

unsigned int pow(int a, int b)
{
    unsigned int res = 1;
    while(b) {
        if(b&1)
            res *= a;
        a *= a;
        b >>= 1;
    }
    return res;
}

Si existe una especie de juego con los bits para calcular un numero a un exponente entonces su complejidad podría ser O(1). Por lo tanto mucho mejor que O(lg(n)).

Bueno, a que viene todo esto?
Realmente seria muy interesante ver un algoritmo que calcula potencias de un número en base a un juego de bits.

Si el profe les llega a dar la respuesta podrías postearla aqui? (Claro, en caso de que nadie mas la ponga)

Saludos!

Un dato importante para que puedas dar con la solucion es que recuerdes que las potencias (en el sistema decimal o en cualquier otro) son sumas de multiplicaciones y las multiplicaciones son igualmente sumas. Ahora, sabes sumar en binario verdad?  ;)

sisi claro que se sumar en binario xD

seguire pensando en alguna relacion que pueda tener ... si termino sabiendo la respuesta sereis los primeros en enteraros por aqui ;)

prometi respuestas pero aun no las tengo
el profesor no se referia a programacion

nos dio una pista...
(a+b)^2 --> binomio de newton

todavia no he tenido tiempo de ponerme a pensar pero este fin de semana espero encontrar la solucion, a no ser que la encuentre alguien antes jaja

en cuanto lo sepa lo pongo ;)