位运算

原码

原码就是符号位加上真值的绝对值, 即用第一位表示符号, 其余位表示值. 比如如果是8位二进制:

其中，第一位为1是负数

[+1] = [0000 0001]原

[-1] = [1000 0001]原

因此，8位二进制数的取值范围：[-127,127]

补码

正数的补码是其本身

负数的补码是在其原码的基础上，符号位不变，其余各位取反，最后+1(即在其反码的基础上+1)

[+1] = [00000001]原 = [00000001]反 = [00000001]补

[-1] = [10000001]原 = [11111110]反 = [11111111]补

反码

正数的反码是其本身

负数的反码是在其原码的基础上，符号位不变，其余各个位取反

[+1] = [00000001]原 = [00000001]反

[-1] = [10000001]原 = [11111110]反

技巧

memset(a, 0x3f, sizeof(a)) 给数组赋值 0x3f3f3f3f

赋值正无穷 INF = 0x3f3f3f3f 或者 INF = 0x3f

移位运算

左移：n << x = n*2^x

右移：n >> x = n/2^x (在C++中右移为算数右移，即移出去的位丢弃，空缺位用“符号位”来填充)

快速幂

原理解释：

代码模板：

int qmi(int m, int k, int p)
{
    int res = 1 % p, t = m;
    while (k)
    {
        if (k&1) res = res * t % p;
        t = t * t % p;
        k >>= 1;
    }
    return res;
}

例题：

AcWing 89. a^b

#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
typedef long long ll;

int main()
{
    ll a,b,p;
    cin>>a>>b>>p;
    ll res = 1;
    while(b)
    {
        if(b&1) res = res * a % p;
        a *= a;
        a %= p;
        b >>= 1;
    }
    cout<<res % p<<endl;

    return 0;
}