numeros binarios

[kaiserr]

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

[Og.]

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²

Código (cpp) [Seleccionar] Expandir

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!

[multiplayer1080]

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?  

[kaiserr]

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

[kaiserr]

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