Thuật toán tính

$a^b$ bình thường nếu chỉ chạy

$b$ lần rồi nhân

$a$ vào kết quả sẽ có độ phức tạp

$O(b)$, không hiệu quả với

$b$ lớn. Đối với thuật toán lũy thừa nhị phân dùng chia để trị chỉ mất độ phức tạp

$O(\log b)$, cực kì hiệu quả.

Thuật toán

Xét ví dụ cần tính

$5^{20}$. Ta có thể phân tích

$5^{20}={\left(5^{10}\right)}^2$. Như vậy ta chỉ cần tính

$5^{10}$ sau đó bình phương lên là được kết quả. Tương tự với

$5^{10}={\left(5^5\right)}^2$, ta chỉ cần tính

$5^5$ rồi bình phương lên để được

$5^{10}$. Với

$5^5$, ta có thể phân tích thành

$5^4\cdot 5={\left(5^2\right)}^2\cdot 5$. Và

$5^2=5^2$. Cuối cùng

$5=5^0\cdot 5$, và ta có base case

$5^0=1$

Vậy ta suy ra được công thức sau:

$$a^b=\{\begin{array}{ll}1& \text{nếu }b=0\\ {\left(a^{\frac{b}{2}}\right)}^2& \text{nếu }b>0\text{ và }b\text{ chẵn}\\ {\left(a^{\lfloor \frac{b}{2}\rfloor }\right)}^2\cdot a& \text{nếu }b>0\text{ và }b\text{ lẻ}\end{array}$$

long long binpow(long long a, long long b) {
    if(b == 0)
        return 1;
    long long res = binpow(a, b / 2);
    res *= res; // res ^ 2
    if(b % 2 == 1)
        res *= a;
    return res;
}

Một cách khác không dùng đệ quy:
Xét ví dụ

$5^{13}$. Trong hệ nhị phân (bits),

$13={1101}_2={1000}_2+{100}_2+1_2=8+4+1\Rightarrow 5^{13}=5^{8+4+1}=5^8\cdot 5^4\cdot 5^1$ (

$a^{b+c}=a^b\cdot a^c$).
Vì trong hệ nhị phân, mỗi bit

$1$ tượng trưng cho một lũy thừa của 2 nên ta sẽ được tích của các lũy thừa với các số mũ là lũy thừa 2.
Xét các bit từ phải qua trái, bit thứ 0 (bit đầu tiên) tượng trưng cho

$5^{(2^0)}$, bit thứ 1 tượng trưng cho

$5^{(2^1)}$, bit thứ 2 tượng trưng cho

$5^{(2^2)}$, …, bit thứ i tượng trưng cho

$5^{(2^i)}$.
Nếu bit thứ 0 được bật (= 1), ta sẽ nhân

$5^{(2^0)}$ vào kết quả, bit thứ 1 được bật thì ta sẽ nhân

$5^{(2^1)}$ vào kết quả, bit thứ i được bật thì ta sẽ nhân

$5^{(2^i)}$ vào kết quả.

long long binpow(long long a, long long b) {
    long long res = 1;
    while(b > 0) {
        if(b & 1) // nếu bit i được bật
            res *= a;
        a *= a; // bình phương a hiện tại để tới bit tiếp theo
        b >>= 1; // dịch 1 bit sang bên phải (tới bit tiếp theo)
    }
    return res;
}

Thông thường, các bài toán sẽ yêu cầu ta tính

$a^{b}modm$ do lũy thừa là một số có thể rất lớn. Ta cũng có thể áp dụng mod vào lũy thừa nhị phân.