快速幂与快速乘

快速幂与快速乘

快速幂

  1. 背景: a ^ n, 需要O(n), 当 n 越大, 时间直线上升, 为此, 提出快速幂
  2. 原理: 利用二进制权值, 有权底数乘指数, 无权指数相乘
  • 举例: 5^11
  • 普通做法: 5相乘11次
  • 快速幂做法: 把11(10)看成1011(2), 则5^11 = 5^(2^3+2^1+2^0), 直接变成三次, 接下来只需要关心怎么实现 2^3+2^1+2^0
  1. 实现: 利用二进制运算符 & 与 >>, 分别为末端取值和移位 ``` int pow_mod(int a, int b) { int ret = 1; while (b) {
    1.  if (b & 1) {
    2.      //如果b & 1 为1, 则说明这一位有值, 或者是有权
    3.      ret *= a;
    4.  } else {
    5.      a *= a;
    6.  }
    7.  b >>= 1;    //b 右移一位
    } }
  1. ### 快速乘
  3. 1. 背景: 当乘数过大, 有可能会爆数据类型的范围, 此时借鉴快速幂把幂变成乘法的做法, 把乘法变成加法(乘法实际上就是加法)
  4. 1. 实现

int mul_mod(int a, int b) { int ret = 0; while (b) { if (b & 1) { //如果b & 1 为1, 则说明这一位有值, 或者是有权 ret += a; } else { a += a; } b >>= 1; //b 右移一位 } return ret; } //因为乘法可以变成快速乘, 那么快速幂里面的乘法就可以直接使用快速乘 int pow_mod(int a, int b) { int ret = 1; while (b) { if (b & 1) { //如果b & 1 为1, 则说明这一位有值, 或者是有权 ret = mul_mod(ret, a); } else { a = mul_mod(a, a); } b >>= 1; //b 右移一位 } return ret; }

```