快速幂为什么每次都变为平方

回复帖子

@EarthGiao 2019-05-15 18:14 回复
int poww(int a, int b) {
    int ans = 1, base = a;
    while (b != 0) {
        if (b & 1 != 0)
            ans *= base;
            base *= base;
            b >>= 1;
    }
    return ans;
}

第6行为什么要开平方

@EarthGiao 2019-05-15 18:25 回复

@LJB00131 二进制不是2的0次方,2的1次方,2的2次方,2的3次方这样的吗?

@Code_Note 2019-05-15 18:28 回复

a^N=(a^2)^(N/2)(a)(a N为奇数是存在)不是吗

@Code_Note 2019-05-15 18:29 回复

a^N=(a^2)^(N/2)(a)(a N为奇数是存在)不是吗

@Code_Note 2019-05-15 18:29 回复

a^N=(a^2)^(N/2)(乘a)(乘a N为奇数是存在)不是吗(MD我不会markdown)

@EarthGiao 2019-05-15 18:33 回复

而且这和每次都开方有什么关系?

@baoyu 2019-05-15 18:38 回复

@EarthGiao 确实是二进制,但被二进制拆分的是指数
比如 $2^8=(2^4)^2$