快速幂

 1 #include <stdio.h>
 2 #include <string.h>
 3 
 4 typedef long long int lli;
 5 
 6 lli power_digui(lli m, lli n) // 递归版
 7 {
 8     if (n == 0) // 任何数的0次方为1
 9         return 1;
10     lli temp = power_digui(m, n >> 1);
11     temp = temp * temp;
12     if (n & 1) // 最低位为1
13         temp = temp * m;
14     return temp;
15 }
16 
17 lli power_normal(lli m, lli n) // 普通版
18 {
19     lli res = 1, base = m;
20     while (n != 0)
21     {
22         if (n & 1) // 最低位为1
23             res *= base;
24         base *= base;
25         n >>= 1;
26     }
27     return res;
28 }
29 int main()
30 {
31     printf("%d\n", power_digui(2, 10));
32     printf("%d\n", power_normal(2, 10));
33     return 0;
34 }