位运算基础

位运算

时间 2019年4月7日 星期日 17:22:41

左移

$$1<<n=2^n$$ $$n<<1=2n$$

很好理解

右移

$$1>>n$$ 开方
$$n>>1=|n/2|$$ 向下取整

-3>>1=-2    
    
3>>1=1

c++中是向0取整 -3/2=-1(|-1.5|)

快速幂

求 $$(a^b)\bmod p$$ $$1<=a,b,p<=10^9$$直接乘会溢出，从二进制角度看待

$$b=b_{k-1} *2^{k-1} + b_{k-2} * 2^{k-2} +…+b_0 * 2^{0}$$

$$a^b=a^{b_{k-1}2^{k-1}} * a^{b_{k-2} * 2^{k-2}}…. *a^{b_0 * 2^{0}} $$

#include<iostream>
using namespace std;
int main(){
    long long a,b,p;
    cin>>a>>b>>p;
    long long ans=1%p;//对1mod任何数都为0
    //a代表每一位二进制的值 b&1值代表的是状态，实际的值还是a，并且每一步都mod避免溢出
    while(b){
        if( b&1 ) ans=ans*a%p;
        a=a*a%p;
        b>>=1;
    }
    cout<<ans;
    return 0;
}

---

同理：
求 $$(a*b)\bmod p$$ $$1<=a,b,p<=10^{18}$$

$$b=b_{k-1} *2^{k-1} + b_{k-2} * 2^{k-2} +…+b_0 * 2^{0}$$

#include<iostream>
using namespace std;
int main(){
    long long a,b,p;
    cin>>a>>b>>p;
    long long ans=0;//对1mod任何数都为0
    //a代表每一位二进制的值 b&1值代表的是状态，实际的值还是a，并且每一步都mod避免溢出
    while(b){
        if( b&1 ) ans+=a%p;
        a=a*2&p;
        b>>=1;
    }
    cout<<ans;
    return 0;
}

另一种方法
$$(ab)\bmod p=(ab)-|a*b/p|p$$
$$|ab/p|$$代表向下取整

#include<iostream>
using namespace std;
int main(){
    long long a,b,p;
    cin>>a>>b>>p;
    long long c=(long double)a*b/p;//运算时保留小数，强制类型转换时保留整数位
    long long ans=a*b-c*p;
    if( ans >= p )  ans-=p;
    else if ( ans < 0 )  ans+=p;
    cout<<ans;
    return 0;
}