一、位运算法则
1.位运算概述
在现代计算机中，所有数据都以二进制形式存储，即 0 和 1 两种状态。计算机对二进制数据进行的运算（如加、减、乘、除）被称为位运算，即对二进制数的每一位进行操作的运算。
对于代码：
int a = 35;
int b = 47;
int c = a + b;计算机会将这两个整数转换为二进制形式，然后进行加法运算：
35: 0010 0011
47: 0010 1111
—————-
82: 0101 0010
因此，与直接使用 +、-、*、/ 运算符相比，合理运用位运算可以显著提高代码在机器上的执行效率。
2.位运算概览
| 符号 | 描述 | 运算规则 |
|---|---|---|
| & | 与 | 两个位都为1时，结果才为1 |
| | | 或 | 两个位都为0时，结果才为0 |
| ^ | 异或 | 两个位相同为0，相异为1 |
| ~ | 取反 | 0变1，1变0 |
| << | 左移 | 各二进位全部左移若干位，高位丢弃，低位补0 |
| >> | 右移 | 各二进位全部右移若干位，高位补0或符号位补齐 |
2.1 按位与运算符（&）
定义：对参与运算的两个数据的二进制位进行”与”运算。
运算规则：
0 & 0 = 0
0 & 1 = 0
1 & 0 = 0
1 & 1 = 1
总结：只有两位同时为1时，结果才为1，否则结果为0。
例如：3 & 5 即 0000 0011 & 0000 0101 = 0000 0001，因此 3 & 5 的值为1。
注意：负数按补码形式参与按位与运算。
用途：
- 清零：如果想将一个单元清零，只要与一个各位都为零的数值相与，结果为零。
- 取一个数的指定位：例如，取数 X = 1010 1110 的低4位，只需另找一个数 Y = 0000 1111，然后 X & Y = 0000 1110 即可得到 X 的指定位。
- 判断奇偶：通过判断最未位是0还是1来决定奇偶，可以用 if ((a & 1) == 0) 代替 if (a % 2 == 0) 来判断 a 是否为偶数。
2.2 按位或运算符（|）
定义：对参与运算的两个对象的二进制位进行”或”运算。
运算规则：
0 | 0 = 0
0 | 1 = 1
1 | 0 = 1
1 | 1 = 1
总结：只要有一个为1，其值为1。
例如：3 | 5 即 0000 0011 | 0000 0101 = 0000 0111，因此 3 | 5 的值为7。
注意：负数按补码形式参与按位或运算。
用途：
- 设置某些位为1：例如，将数 X = 1010 1110 的低4位设置为1，只需另找一个数 Y = 0000 1111，然后 X | Y = 1010 1111 即可得到。
2.3 异或运算符（^）
定义：对参与运算的两个数据的二进制位进行”异或”运算。
运算规则：
0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0
总结：相应位相同为0，相异为1。
性质：
- 交换律
- 结合律： (a ^ b) ^ c == a ^ (b ^ c)
- 对于任何数 x，都有 x ^ x = 0，x ^ 0 = x
- 自反性：a ^ b ^ b = a ^ 0 = a
用途：
- 翻转指定位：例如，将数 X = 1010 1110 的低4位翻转，只需另找一个数 Y = 0000 1111，然后 X ^ Y = 1010 0001 即可得到。
- 与0相异或值不变：例如 1010 1110 ^ 0000 0000 = 1010 1110
- 交换两个数：
void Swap(int &a, int &b) {
if (a != b) {
a ^= b;
b ^= a;
a ^= b;
}
}2.4 取反运算符（~）
定义：对参与运算的一个数据的二进制位进行”取反”运算。
运算规则：
~1 = 1111 1110
~0 = 1111 1111
即
~1 = -2
~0 = -1
总结：将 0 变 1，1 变 0。
用途：
- 使一个数的最低位为零：例如，使 a 的最低位为0，可以表示为：a & ~1。~1 的值为 1111 1111 1111 1110，再按”与”运算，最低位一定为0。
2.5 左右移运算符（<< 和 >>）
定义：将一个运算对象的各二进制位全部左移若干位，高位丢弃，低位补0。
例如，设 a = 1010 1110，a = a << 2 将 a 的二进制位左移2位、右补0，即得 a = 1011 1000。
若左移时舍弃的高位不包含1，则每左移一位，相当于该数乘以2。
将一个数的各二进制位全部右移若干位，高位补0或补符号位，右边丢弃。
例如，a = a >> 2 将 a 的二进制位右移2位，左补0 或补符号位，具体取决于数的正负。
操作数每右移一位，相当于该数除以2。
用途：
- 快速乘除：左移相当于乘以2的幂，右移相当于除以2的幂
int a = 10;
int b = a << 2; // 相当于 a * 4 = 40
int c = a >> 1; // 相当于 a / 2 = 52.6 复合赋值运算符
位运算符与赋值运算符结合，组成新的复合赋值运算符，它们是：
- &= 例：a &= b 相当于 a = a & b
- |= 例：a |= b 相当于 a = a | b
- >>= 例：a >>= b 相当于 a = a >> b
- <<= 例：a <<= b 相当于 a = a << b
- ^= 例：a ^= b 相当于 a = a ^ b
运算规则与前述的复合赋值运算符的运算规则相似。
不同长度的数据进行位运算：
如果两个不同长度的数据进行位运算，系统会将二者按右端对齐，然后进行位运算。
以”与运算”为例说明如下：
在 C++ 中，当整型类型小于 int 时，运算前会先进行整型提升。对于位运算，当两个不同类型的整数进行运算时，较小类型会提升到较大类型：
- 如果有符号源类型为正数或零：高位补 0（零扩展）
- 如果有符号源类型为负数：高位补符号位（符号扩展）
- 如果源类型为无符号类型：高位补 0（零扩展）
例如：
int32_t a = 123;
uint16_t b = 1;
int32_t result = a & static_cast<int32_t>(b); // b 被提升，高位补0下面给出按位异或的几个能开阔思维的题目：
https://ac.nowcoder.com/acm/contest/85639/D
https://codeforces.com/contest/2225/problem/D
学会了前置知识，我们就能迅速理解正篇——快速幂算法。
二、快速幂
快速幂（fast exponentiation），也称 二进制取幂（binary exponentiation）或 平方取幂法（exponentiation by squaring），是一个在 O(log𝑛)的时间内计算 的小技巧，而暴力的计算需要 O(𝑛)的时间．
快速幂算法的核心思想就是每一步都把指数分成两半，而相应的底数做平方运算。这样不仅能把非常大的指数给不断变小，所需要执行的循环次数也变小，而最后表示的结果却一直不会变。
例如计算我们可以表示为
不难发现
- 如果指数是是偶数，那么指数除以2，底数平方，前后的值相等。（）
- 如果指数是奇数，将ans*=底数，再指数除以2，底数平方，前后值相同。（）
由于每一次操作都回使指数/2，假如指数大小是b，则暴力要循环b次，而通过快速幂，我们成功优化为O（logb），即以2为底，b的对数。这个优化显然是巨幅的，那么代码上怎么实现呢？
ll qpow(ll a, ll b, ll mod)
{
ll res = 1; // 初始化结果为1（任何数的0次幂为1）
a %= mod; // 避免后续乘法溢出同时防止输入的a过大
// 当指数b不为0时继续计算
while (b)
{
if (b % 2 == 1)
{
res *= a; // 将当前幂乘入结果
res %= mod; // 每次乘法后取模，保证结果在模c范围内
}
a *= a; // 计算下一位的幂：a^(2^k)
a %= mod; // 平方后取模，防止溢出
b /= 2;
}
return res; // 返回最终结果
}
// 使用前需要确保已定义 ll 为 long long 的别名看到这我们不妨回想一下前文提到的位运算，判断指数是偶数还是奇数，还有一种更高效的方法就是使用位运算中的与（&）运算，因为1的补码只有最后一位为1，其余全为0。如果b是奇数的话，那它的最后一位为1，b&1的结果就是1，如果b是偶数，那最后一位为0，b&1的结果是0。
同时b/=2这里，我们可以用b >>= 1代替（整数算术右移一位相当于除以2并向下取整）。
故而我们得到快速幂最终版本：
ll qpow(ll a, ll b, ll mod)
{
ll res = 1;
a %= mod;
while (b)
{
if (b & 1)
res = res * a % mod; // 当前位为1时累乘
a = a * a % mod; // 底数平方
b >>= 1; // 指数右移
}
return res;
}相关习题待我优选后列出，下一篇见~
