La exponenciación rápida es una técnica que permite calcular potencias con complejidad temporal O(log n) en lugar de O(n), mediante el uso de la representación binaria del exponente. Esto se basa en descomponer el exponente en sumas de potencias de 2, lo que reduce significativamente el número de multiplicaciones necesarias.

Por ejemplo, para calcular a^b, si b se expresa en binario como d_k d_{k-1} ... d_0, entonces a^b = Π (a^(2^i)) para todos los i donde d_i = 1. Esto aprovecha que a^(2^i) se puede calcular iterativamente mediante exponentiación por cuadrado.

A continuación se presenta una implementación en C que utiliza un arreglo para almacenar los bits del exponente y las potencias acumuladas:

#include <stdio.h>

long long calcular_potencia_rapida(long long base, long long exponente) {
    int almacen_bits[64][2]; // Almacena bits y potencias correspondientes
    int num_bits = 0;
    long long resultado = 1;
    long long temp_exp = exponente;
    
    // Conversión a binario y almacenamiento de bits
    do {
        almacen_bits[num_bits][0] = temp_exp % 2;
        temp_exp /= 2;
        num_bits++;
    } while (temp_exp > 0);
    
    // Cálculo progresivo de potencias de la base
    almacen_bits[0][1] = base;
    for (int i = 1; i < num_bits; i++) {
        almacen_bits[i][1] = almacen_bits[i-1][1] * almacen_bits[i-1][1];
    }
    
    // Multiplicación de factores según bits activados
    for (int i = 0; i < num_bits; i++) {
        if (almacen_bits[i][0]) {
            resultado *= almacen_bits[i][1];
        }
    }
    
    return resultado;
}

int main() {
    long long base, exp;
    scanf("%lld %lld", &base, &exp);
    printf("%lld", calcular_potencia_rapida(base, exp));
    return 0;
}

Esta versión tiene compeljidad espacial O(log n) debido al arreglo. Una optimización común utiliza operaciones bit a bit para eliminar la necesidad de almacenamiento adicional, manteniendo el mismo tiempo pero con espacio O(1).

El código optimizado emplea desplazamiento de bits y operaciones AND para procesar cada bit del exponente directamente:

#include <stdio.h>

long long potencia_optimizada_bitwise(long long base, long long exponente) {
    long long res = 1;
    while (exponente > 0) {
        if (exponente & 1) { // Verifica el bit menos significativo
            res *= base;
        }
        base *= base; // Cuadrado de la base para la siguiente potencia
        exponente >>= 1; // Desplazamiento a la derecha
    }
    return res;
}

int main() {
    long long a, b;
    scanf("%lld %lld", &a, &b);
    printf("%lld", potencia_optimizada_bitwise(a, b));
    return 0;
}

Este método es ampliamente utilizado en algoritmos que requieren cálculos de potencias grandes, como en criptografía RSA o computación modular, donde la eficiencia es crítica. La elección entre implementaciones depende de las restricciones de memoria y los requisitos específicos del entorno de ejecución.