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{cases} 1 &\text{nếu } b = 0 \\ \left(a^{b \over 2}\right)^2 &\text{nếu } b > 0 \text{ và } b \text{ chẵn} \\ \left(a^{\left\lfloor b \over 2 \right\rfloor}\right)^2 \cdot a &\text{nếu } b > 0 \text{ và } b \text{ lẻ} \end{cases}$$

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 \bmod m$ do lũy thừa là một số có thể rất lớn. Ta cũng có thể áp dụng [mod](https://hackmd.io/@khoad/S1R3wgcBa) vào lũy thừa nhị phân.