# 最直观的方法

5 ^ 55


# 效率高的求法

5 ^ 2 = 5 * 5
5 ^ 4 = (5 ^ 2) * (5 ^ 2)
5 ^ 8 = (5 ^ 4) * (5 ^ 4)
5 ^ 16 = (5 ^ 8) * (5 ^ 8)
5 ^ 32 = (5 ^ 16) * (5 ^ 16)

5 ^ 55 = 5 ^ (32 + 16 + 4 + 2 + 1)
= 5 ^ 32 * 5 ^ 16 * 5 ^ 4 * 5 ^ 2 * 5


# 神奇的二进制

0011 0111


我们从最低位开始，如果为1,则乘以这个位的2次幂，否则跳过。


# 倒转任意进制数

#include <stdio.h>

/* reverse a number NUM with base BASE,
* return the reversed number in decimal. */
int reverse_num(int base, int num);

int main(int argc, char *argv[])
{
printf("%d\n", reverse_num(10, 15));
printf("%#x\n", reverse_num(16, 0x32));

return 0;
}

int reverse_num(int base, int num)
{
int new_num;

new_num = 0;
while (num > 0) {
new_num *= base;
new_num += (num % base);
num /= base;
}
return new_num;
}


# 较高效的整数求幂法

#include <stdio.h>

/* calculate NUM ^ EXP，return the result */
long long qpow(int num, int exp);

int main(int argc, char *argv[])
{
printf("%lld\n", qpow(5, 20));

return 0;
}

long long qpow(int num, int exp)
{
long long pow, base;

pow = 1;
base = num;        //long may not be able to hold
while (exp > 0) {
if ((exp & 1) == 1) {   // (exp % 2) == 1
pow *= base;
}
base *= base;
exp >>= 1;        // exp /= 2;
}
return pow;
}