位运算基础知识及简单例题（待补全Hamilton）

位运算

+++

1 : 0000000000...01

2 : 0000000000...10

3 : 0000000000...11

• 补码

1 + x = 0000000000...00

1 + 1111111111111...11 = 00000000000...00

2 + 1111111111111...10 = 00000000000...00

x + ?

? = ~x + 1

~x + 1是 x 的补码

-n = ~n + 1

//左移
1 << n     -----------   ==   2 ^ n   
1 -> 10 -> 100
//右移
n >> x     -----------   ==   n / 2 ^ x

+++

Ignore me : #include<bits/stdc++.h>

+++

• 快速幂

1.求 a ^ b mod p 89

#include <iostream>

using namespace std;

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

2.64位整数乘法 90

#include <iostream>

using namespace std;

typedef unsigned long long ULL;

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