从快速幂方法到位运算中的左移右移

一般的幂运算是对底数连乘，时间复杂度为O(n)，在进行高幂运算时会影响程序执行效率，故需要利用快速幂。快速幂方法是对指数进行分解，再进行运算。如2^10分解为: 2^2 * 2^2 *2^2 * 2^2 *2^2。使复杂度降为O(logn)。
一般实现方法有两种，一是递归实现，二是通过位运算

递归实现快速幂

def f1(a,n):
    if n==1:
        return a
    if n%2==1:
        return f1(a,n//2)*f1(a,n//2)*a
    else:
        return f1(a,n//2)*f1(a,n//2)
print(f1(2,100))

位运算（左移）实现快速幂

n=100
a=2
ans=1
while n:
    if n&1: # 判断奇偶，
        ans*=a  # 奇数情况
    a*=a  # 偶数情况
    n>>=1  # 指数右移一位
print(ans)

其中位运算的左移、右移操作即对二进制数左移、右移，可转换为对十进制数的操作。

位运算中的左移与右移

左移操作<<，左移b位相当于乘以2的b次方，a<<b,a’ = a*(2^b)。

print(2<<3) # 2*2^3 = 16，2的二进制10，向左移动3位后10000
print(2<<1) # 2*2^1 = 4
print(3<<4) # 3*2^4 = 48,3的二进制为11，向左移动四位后110000

右移操作>>，右移b位相当于除以2的b次方,a<<b,a’ = a//(2^b)注意这里是整除，当向右移动位数大于能移动的位数时，置为0。

print(2>>3) # 2//2^3 = 0，2的二进制10，向右最多移动2位后，所以多移动无疑为0
print(2>>1) # 2//2^1 = 1，向右移动一位为01,
print(3>>4) # 3//2^4 = 0,3的二进制为11，向右移动四位后00
print(3>>1) # 3//2^1 = 1,3的二进制为11，向右移动一位后为01

为什么使用位运算，而不是直接用十进制数？
计算机实际是对二进制数进行处理，直接采用对二进制数操作的的位运算能提高程序运算效率。

参考博客：
彻底理解位运算——左移、右移
【Python位运算】——左移操作（＜＜）右移操作＞＞
【Python 百练成钢】快速幂合集

最后

以上就是微笑小虾米为你收集整理的python 从快速幂方法到位运算中的左移右移从快速幂方法到位运算中的左移右移的全部内容，希望文章能够帮你解决python 从快速幂方法到位运算中的左移右移从快速幂方法到位运算中的左移右移所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。