快速幂
问题：
给定整数 \(a,\ b,\ p\) 计算 \(a^b\mod p\) \((1 \le a,b,p \le 10^9)\)
分析：
我们可以将 \(b\) 转换成二进制：
\[b = c_02^0+c_12^1+c_22^2+...+c_{k-1}2^{k-1} \]其中 \(c_n\) 的取值为 \(0\) 或者 \(1\)
那么有：
\[a^b = a^{c_02^0+c_12^1+c_22^2+...+c_{k-1}2^{k-1}} \]\[a^b = a^{c_02^0}a^{c_12^1}a^{c_22^2}...a^{c_{k-1}2^{k-1}} \]并且我们知道
\[a^{2^{n}} = (a^{2^{n-1}})^2 \]故我们只需要递推即可得出每个乘积项，当 \(c_n = 1\) 时累积到答案中即可。
代码：
int quickPower(int a, int b, int p) {
int ans = 1 % p;
while (b) {
if (b & 1) ans = (long long)ans * a % p;
b >>= 1;
a = (long long)a * a % p;
}
return ans;
}
例题:
龟速乘
问题：
给定整数 \(a,\ b,\ p\) 计算 \(a\times b\mod p\) \((1 \le a,b,p \le 10^{18})\)
分析：
由于long long只能存 \(9\times 10^{18}\) 这么大的数，所以我们要想办法让计算不溢出。根据快速幂的思想，我们可以把 \(b\) 分解成二进制
\[b = c_02^0+c_12^1+c_22^2+...+c_{k-1}2^{k-1} \]然后有
\[a\times b = c_0a2^0+c_1a2^1+c_2a2^2+...+c_{k-1}a2^{k-1} \]又因为
\[a2^n = (a2^{n-1})\times 2 \]如果我们得到 \(a2^{n-1}\mod p\) ，然后计算 \((a2^{n-1})\times 2 \mod p\) 可以保证每一步都不溢出
同样当 \(c_i = 1\) 时将乘积项累加到答案中即可
代码：
long long mul(long long a, long long b, long long p) {
long long ans = 0;
while (b) {
if (b & 1) ans = (ans + a) % p;
a = (a * 2) % p;
b >>= 1;
}
return ans;
}
例题：
二进制状态压缩
将一个长度为 \(m\) 的 bool 数组用一个二进制整数表示并存储。
利用位运算实现原 bool 数组中对应下标元素的存取。
| 操作 | 运算 |
|---|---|
| 取出 \(n\) 的第 \(k\) 位 | (n>>k) & 1 |
| 取出 \(n\) 的第 \(0\) ~ \(k-1\) 位（后 \(k\) 位） | n & ((1<<k)-1) |
| 将第 \(k\) 位取反 | n xor (1<<k) |
| 将第 \(k\) 位赋值 \(1\) | n | (1<<k) |
| 将第 \(k\) 位赋值 \(0\) | n & (~(1<<k)) |
位运算的一个重要特点：在二进制表示下不进位，参与位运算的各个二进制位之间是独立无关的
例题：
成对变换
对于非负整数 \(n\) ，我们发现：
当 \(n\) 为奇数时，\(n\ xor\ 1 = n-1\)
当 \(n\) 为偶数时，\(n\ xor\ 1 = n+1\)
因此，0和1、2和3、4和5...都是关于xor 1运算成对变换
常用于邻接表中无向边的存取
lowbit运算
lowbit(n) 定义为非负整数 \(n\) 在二进制表示下“最低位的 \(1\) 及其后边的所有 \(0\)”构成的数值。
因为在计算机中 \([-x]_补 = [x]_补\ 按位取反 + 1\)
所以有
\[lowbit(n) = n\ \&\ (\sim n+1) = n\ \&\ (-n) \]通过 lowbit 运算，我们可以找到整数二进制表示下所有是 \(1\) 的位：
迭代计算 \(n = n - lowbit(n)\) 直到 \(n\) 为 \(0\)，减掉的数就是所有二进制是 \(1\) 的位与后面的 \(0\) 构成的数值，然后通过取对数 \(log_2x\) 即可得出位置。
这里求对数可以预处理，建立一个长度为 \(37\) 的数组 \(H\) ，令 \(H[2^k \mod 37] = k\) ，有一个小技巧，\(\forall k \in [0,35], 2^k \mod 37\) 互不相等。
int H[37];
for (int i=0;i<37;i++) H[(1ll << i) % 37] = i;
while (cin >> n) {
while (n > 0) {
cout << H[(n & -n) % 37];
n -= (n & -n);
}
}
lowbit也是树状数组的一个基本运算
标签：运算,int,long,二进制,算法,应用,ans,mod From： https://www.cnblogs.com/juniexd/p/17990961