题解 | #数值的整数次方#
数值的整数次方
http://www.nowcoder.com/practice/1a834e5e3e1a4b7ba251417554e07c00
- 题目描述
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
保证base和exponent不同时为0。不得使用库函数，同时不需要考虑大数问题，也不用考虑小数点后面0的位数。
- 思路
一个数末尾为0时，右移一位相当于除以2,
一个数末尾为1时，右移一位相当于-1，再除以2
所以，当exponent&1=1时，需要将resbase，再令exponent右移1位，exponent右移1位的本质是base^exponent = base^(2exponent/2) = (base^2)^(exponent/2)，因此，base=base^2。 - 算法流程
假设 base=3，exponent= 5。那么 5 的二进制是：101
- 结果值 result 初始为 1
- base 初始为 3，此时 exponent 的二进制最右位为 1，更新结果为：base * result
- exponent 右移一位。base 进行累乘，base 更新为 3 的 2 次方。由于 exponent 的二进制最右位为 0，不更新结果
- exponent 右移一位。base 进行累乘，base 更新为 3 的 4 次方。此时 exponent 的二进制最右位为 1，更新结果为：base * result，再右移，exponent则为0，程序结束
