本文章原出处：chicago01.top，转载不需说明，随意转载

基本操作

与   &   都为真为真
或   |   有一个为真就为真
非   !   真的变假，假的变真
异或  ^   如果相同为0，不同为1

补码

int 32位 首位符号位，如果是0为正数，为1为负数。

1: 0000000000...01
2: 0000000000...10
3: 0000000000...11

补码：

[HTML_REMOVED]

1 + x = 000000000...00
x = 1111111111...11
1 + 1111111111...11 = 0000000000...00
2 + 1111111111...10 = 0000000000...00
x + ??????????...?? = 0000000000...00
? = ~x + 1
~x + 1 是 x 的补码
-n = ~n + 1

小技巧

• 数组初始化memset(f,0x3f,sizeof(f))
• 左移运算符 <<

二进制 ： 1 -> 10 -> 100 -> 1000
十进制 ： 1 -> 2  -> 4   -> 8
综上所述：1 << n  ==  2^n

• 右移运算符>>

二进制 ： 1000 -> 100 -> 10 -> 1
十进制 :  8    -> 4   -> 2  -> 1
综上所述: n >> x  == n / (2^x)

例题1a^b快速幂

求 a 的 b 次方对 p 取模的值。

输入格式

三个整数 a,b,p,在同一行用空格隔开。

输出格式

输出一个整数，表示a^b mod p的值。

数据范围

$1≤a,b,p≤10^9$

输入样例：

3 2 7

输出样例：

2

题解：

按照朴素算法就是把a连乘b次，这样一来时间复杂度是O(b)也即是O(n)级别，快速幂能做到O(logn)。

$a^b$，那么其实b是可以拆成二进制的，该二进制数第i位的权为$2^{(i-1)}$，例如当b==11时，$a^{11}=a^{(2^0+2^1+2^3)}$ 。

11的二进制是1011，11 = 2³×1 + 2²×0 + 2¹×1 + 2º×1，因此，我们将a¹¹转化为算 $a^(2^0)*a^(2^1)*a^(2^3) $ 。

由于是二进制，很自然地想到用位运算这个强大的工具： &  和 >> ，&运算通常用于二进制取位操作，例如一个数 & 1 的结果就是取二进制的最末位。还可以判断奇偶x&1==0为偶，x&1==1为奇。>>运算比较单纯,二进制去掉最后一位 。

代码：

#include<bits/stdc++.h>
using namespace std;

int a,b,mod;

int main(void)
{
    cin >> a >> b >> mod;

    int res = 1 % mod;

    while(b)
    {
        if(b&1) res = 1ll * res * a % mod;

        a = 1ll * a * a % mod;
        b >>= 1;
    }

    cout << res;
    return 0;
}

例题2:64位整数乘法

求 a 乘 b 对 p 取模的值。

输入格式

第一行输入整数aa，第二行输入整数bb，第三行输入整数pp。

输出格式

输出一个整数，表示a*b mod p的值。

数据范围

1≤a,b,p≤10181≤a,b,p≤1018

输入样例：

3
4
5

输出样例：

2

题解：

a * b
a + a + a + a + a + a +...+ a
a * 1 = a
a * 2 = 2a
a * 3 = 3a
...
a * (2^k) = 2^k * a

代码：

#include<bits/stdc++.h>
using namespace std;

long long a,b,mod;

int main(void)
{
    cin >> a >> b >> mod;
    long long ans;
    while(b)
    {
        if(b&1) ans = (ans + a) % mod;
        a = a * 2 % mod;
        b >>= 1;
    }
    cout << ans << endl;

    return 0;
}