a021: 大數運算-3

a021: 大數運算-3

'''先举个例子，假如希望求 5^62，也就是 5 的 62 次方。
5^62 = 5^(32+16+8+4+2) = 5^32 * 5^16 * 5^8 * 5^4 * 5^2
不管指数是多少，都可以将其分解为 2 的倍数的和，
因为任何整数都能够写成 2 进制的形式
，比如 62 = 00111110B。以上算法中，
随着迭代 n 会变成 x, x^2, x^4, x^8,…，
我们只需要在合适的时候让它和 ans 相乘即可。
合适的时刻就是 N 的二进制表示的相应位上为 1 的时候，
这里使用了右移，只需要判断最低位是不是 1 就好了。'''

def pow(int_x, N):
    ans = 1
    n = int_x
    while (N != 0):
        if (N & 1 == 1):
            ans = ans * n;
        
        n = n * n;
        N >>= 1;
    
    return ans;


print(" a的 b次方 ==> a^b  計算")
X=int(input("輸入 a > "))
Y=int(input("輸入 b > "))

print("a^b = ",pow(X,Y))

================ RESTART: F:/Python_APSC/a021-4.py ===================
 a的 b次方 ==> a^b  計算
輸入 a > 5
輸入 b > 62
a^b =  21684043449710088680149056017398834228515625
>>>