快速幂

求a^b，朴素算法就是把a连乘b次，这样一来时间复杂度是O(b)也即是O(n)级别，快速幂能做到O(logn)。

a¹¹=a^{(2^0+2^1+2^3)}

11的二进制是1011，11 = 2³×1 + 2²×0 + 2¹×1 + 2º×1

因此，a¹¹ = a^{2^0}*a^{2^1}*a^{2^3}= a¹*a²*a⁸

 1 int poww(int a, int b) {
 2     int ans = 1, base = a;
 3     while (b != 0) {
 4         if (b & 1) ans *= base;
 6         base *= base;
 7         b >>= 1;
 8     }
 9     return ans;
10 }

base*=base这一步：因为 base*base==base²

base²*base²==base⁴（到这一步的时候，由于二进制该位是0，所以就没有计算ans）

base⁴*base⁴=base⁸