C++ 算法学习——1.8 快速幂算法

背景知识:

1.位运算

在C++中,位运算是对整数类型的位进行操作的一种运算方式。常见的位运算符包括按位与(&)、按位或(|)、按位异或(^)、取反(~)、左移(<<)和右移(>>)等。这些运算符可以用来对整数的二进制表示进行操作,实现一些特定功能。下面是对常见位运算操作的简要解释:

  1. 按位与(&):将两个数的对应位都为1的情况下得到1,否则为0。

    例如:5 & 3 的结果是 1,因为 5 的二进制表示是 1013 的二进制表示是 011,按位与后得到 001,即 1

  2. 按位或(|):将两个数的对应位只要有一个为1就得到1,否则为0。

    例如:5 | 3 的结果是 7,因为 5 的二进制表示是 1013 的二进制表示是 011,按位或后得到 111,即 7

  3. 按位异或(^):将两个数的对应位相异时得到1,相同时得到0。

    例如:5 ^ 3 的结果是 6,因为 5 的二进制表示是 1013 的二进制表示是 011,按位异或后得到 110,即 6

  4. 取反(~):对操作数的每一位取反(0变1,1变0)。

    例如:~5 的结果是 -6,因为 5 的二进制表示是 000...0101,取反后得到 111...1010,这是补码表示,转换为十进制即为 -6

  5. 左移(<<):将一个数的二进制表示向左移动指定的位数。

    例如:5 << 1 的结果是 10,因为将 5 的二进制表示 101 向左移动一位得到 1010,即 10

  6. 右移(>>):将一个数的二进制表示向右移动指定的位数。

    例如:5 >> 1 的结果是 2,因为将 5 的二进制表示 101 向右移动一位得到 10,即 2

 2.快速幂的原理

快速幂算法的基本思想是利用二进制分解来减少运算次数。具体步骤如下:

  1. 将指数 n 转化为二进制形式。
  2. 从二进制形式的最低位开始,依次检查每一位:
    • 如果该位为 1,则乘以当前的幂值 base
    • 如果该位为 0,则不进行乘法操作。
  3. 每次处理完一位,将底数 base 自乘一次,表示底数的幂次增加一倍。
  4. 继续处理下一位,直到处理完所有位。

 举个例子:

计算 3^5,以下是上述抽象过程的演示:

  1. 首先,将指数 5 转换为二进制形式:5 的二进制表示为 101。

  2. 从二进制形式的最低位开始逐位处理:

    • 初始时,底数为 3,ans为 1。
    • 第一位为 1,ans乘以当前的幂值 3:结果为 3。base自乘一次为9。
    • 第二位为 0,不进行乘法操作,底数自乘一次:底数变为81,ans不动。
    • 第三位为 1,ans乘以当前的底数81,ans变为3×81=243。

其次引入核心问题。

P1. 洛谷p1226快速幂

long long fastPowerMod(long long base, long long exponent, long long c) {
    long long result = 1;
    
    base = base % c;  // Take base mod c to handle large base values
    
    while (exponent > 0) {
        if (exponent & 1) {  // Check if the current bit is 1
            result = (result * base) % c;
        }
        
        base = (base * base) % c;  // Square the base and take mod c
        exponent = exponent >> 1;  // Shift the bits of the exponent to the right
    }
    
    return result;
}

上一篇:Springboot3+druid+jasypt+application.yml配置文件数据库密码加密技术


下一篇:【Azure Cloud Service】使用RESTAPI更新Cloud Service(Extended Support) 中所配置的证书