首先这个程序是错的，pw%2==1 应该改成 n%2==1
给你举个栗子。
2^21=(2^16)×(2^4)×(2^1)
将n=21用二进制表示也就是(10101)2, 每个1都代表计算2^21要用到的幂次（分别是2^16, 2^4和2^1），每个0代表计算2^21不需要用的幂次（分别是2^8和2^2）.
计算2^13的步骤就是
x=2=2^1, 因为n 的最低位是1， 所以把这部分累乘到pw中。
x自乘后变成2^2, 因为n 的这一位是0，所以跳过不管。
x自乘后变成2^4, 因为n 的这一位是1，所以累乘到pw中。
x自乘后变成2^8, 因为n 的这一位是0，所以跳过不管。
x自乘后变成2^16, 因为n 的这一位是1，所以累乘到pw中。
这是快速求幂的思想，把指数n 分解为2的幂次的和，利用自乘计算x 的(2的幂次)次方, 然后根据需要决定是否累乘相应的幂次。这样可以把O(n)次乘法缩短到O(logn)次乘法，实现快速计算。n/=2和 (n%2==1)是检查指数n 的某个二进制位是否是1的手段。
内容全部来源于网络收集，如有侵权，请联系网站删除！