位运算相关

一些小技巧

一. 利用位运算做乘法

面试题 08.05. 递归乘法

若有两个数字A和B，要求不使用乘法的情况下完成A*B操作。

方法一：递归+加法(非位运算)

int multiply(int A, int B) {
    if(A==0) return 0;
    return multiply(A-1,B)+B;
}

这种做法固然可以求出A*B，但是当A的数值特别大时就会爆栈。并且如果不爆栈，也会因为A的数值过大而导致计算速度过慢。

方法二：递归+位运算

这种方法利用了位运算，相比方法一很大程度提高了计算速度。

问题:

现有数字A和数字B，欲计算A*B，并将结果保存到变量ret中

具体步骤:

1. 先将A和B转换为二进制表示
2. 若A的最后一个位是1，ret = ret + B，若A的最后一个位是0，则不对ret做任何处理
3. 将A位右移一个位，将B位左移一个位
4. 重复步骤2，3直到A变成0，此时ret保存的即为A*B的结果

算法的c语言递归描述如下:

int multiply(int A, int B) {
    if(A == 0) return 0;
    if(A & 1){
        return multiply(A>>1, B<<1) + B;
    } else {
        return multiply(A>>1, B<<1);
    }
}

举个例子

假设现在要计算5*2，数字5和2分别表示为A和B，ret=0

1. 将A转换为二进制表示(0000 0101)，将B转换为二进制表示(0000 0010)
2. 此时A的最后一个位是1(0000 0101)，则ret = ret + 2 = 2. 将A右移一个位得到2(0000 0010)，将B左移一个位得到4(0000 0100)
3. 此时A的最后一个位是1(0000 0010)，则ret不做处理，其值仍等于2. 将A右移一个位得到1(0000 0001)，将B左移一个位得到8(0000 1000)
4. 此时A的最后一个位是1(0000 0001)，则ret = ret + 8 = 10. 将A右移一个位得到0(0000 0000)，将B左移一个位得到16(0001 0000)
5. 由于A已经等于0，跳出循环，得到A*B的结果ret，即10

缺点

当数字B特别大时，左移还是会造成数据溢出

二. 位运算的其他应用

1. 大数相乘取模

现有三个大数A,B和m，求(A*B)\ mod\ m

如果我们直接使用乘法运算符将数字相乘后再取模则肯定会数据溢出，如求 314882150829468584 和 427197303358170108 相乘后对 2009731336725594113 取模的结果

这时可用大数相乘取模算法计算

原理:

算法的c语言描述如下:

typedef long long ll;
ll f(ll a,ll b,ll m){
    ll ret = 0;	//保存答案
    while(b != 0){
        if(b & 1) ret = (ret + a) % m;			
        a = (a << 1) % m;					
        b >>= 1;							
    }
    return ret;
}

2. 快速幂

现有数字A和B，求A^B，答案保存在变量ret中

原理:

具体步骤:

1. 将B转换为二进制表示，此时有B=2^a+2^b+…+2^k，如11=(0000 \ 1011)_2=2^0+2^1+2^3=1+2+8
2. 若B的最后一个位是1，则ret=ret*A，若为0，则ret不做任何处理
3. 令A=A*A，B=B>>1
4. 重复步骤2，3直到B=0

举个栗子

A=2,B=5，计算A^B，答案保存在ret

1. 5=(0000\ 0101)_2=2^0+2^2=1+4
2. B的最后一位是1，则ret=ret * A=2,A=2 * 2=4,B=5>>1=2
3. B的最后一位是0，则ret不做处理，A=4*4=16,B=2>>1=1
4. B的最后一位是1，则ret=ret*A=32,A=16*16=256,B=1>>1=0
5. B=0，跳出循环

上述过程即为

红色为每一次迭代ret的值,蓝色是每一次迭代A的值

或者再来一个例:

算法的c语言描述如下:

typedef long long ll;
ll fastPower(ll base, ll exp){
    ll ret = 1;	//保存答案
    while(exp != 0){
        if(exp & 1) ret *= base;
        base *= base;
        exp >>= 1;
    }
    return ret;
}

3. 快速幂取模

现有三个大数A和B，m，求(A^B)\ mod\ m

针对大数，若直接使用幂运算符计算再取模则很可能会数据溢出

原理:

这篇关于快速幂取模的原理推理写的很好

算法的c语言描述如下:

typedef long long ll;
ll f(ll base, ll exp, ll m){
    ll ret = 1;	//保存答案
    base = base % m;
    while(exp){
        if(exp & 1) ret = (ret * base) % m;
        exp >>= 1;
        base = (base * base) % m;
    }
    return ret;
}

三. 参考与推荐

https://blog.csdn.net/qq_19782019/article/details/85621386

https://blog.csdn.net/qq_36760780/article/details/80092665