[[bit]]：度量信息的单位，只有0和1。
[[位运算]]：与 或 非 异或——不只局限于逻辑运算。它们均可作用于[[二进制数]]
例题
E-起床困难综合症_0x01 基本算法-位运算
朴素算法：枚举0~m,求最大f(m)：O(n*m)
利用位运算的分配律，将要枚举的m'拆成二次幂，然后进行枚举:O(2log2(m) n)
int k = log2(m);
for (int j = k; j >= 0; j--)
{
for (int i = 1; i <= n; i++)
{
if (oop[i] == 1)
ans[j] = ans[j] | ((t[i] >> j) & 1);
else if (oop[i] == 2)
ans[j] = ans[j] & ((t[i] >> j) & 1);
else if (oop[i] == 3)
ans[j] = ans[j] ^ ((t[i] >> j) & 1);
}
if (ans[j] == 0)
{
ans[j] = 1;
for (int i = 1; i <= n; i++)
{
if (oop[i] == 1)
ans[j] = ans[j] | ((t[i] >> j) & 1);
else if (oop[i] == 2)
ans[j] = ans[j] & ((t[i] >> j) & 1);
else if (oop[i] == 3)
ans[j] = ans[j] ^ ((t[i] >> j) & 1);
}
if (ans[j] == 1)
{
if (res + (1 << j) <= m)
res += (1 << j);
else
continue;
}
}
}
[[补码]]: “二补码”
[[移位运算]]:代替2的幂次的乘除
例题
快速幂 #快速幂
A-a^b_0x01 基本算法-位运算
![Pasted image 20260424192348.png]]
对b转化为二进制，而a的2次幂的幂可以由递推得到：
![Pasted image 20260424192439.png]]
可以得到以下代码：
int power(int a, int b, int p) //a^b (mod p)
{
int val = 1;
while (b > 0)
{
if (b & 1)
val = (val * a) % p;
b >>= 1;
a = (a * a) % p;
}
return val;
}
64位整数乘法
C-64位整数乘法_0x01 基本算法-位运算
[法一：与快速幂类似，将b拆成二次幂相加]
#define ll long long
ll multiply(ll a,ll b,ll p)
{
ll val=0;
a=a%p;
b=b%p;
while(b)
{
if(b&1)
val=(val+a)%p;
a=(a*2)%p;
b>>=1;
}
return val;
}
[法二：]
我不理解
![Pasted image 20260424201221.png]]
[[二进制状态压缩]]：用二进制数存储bool数组
例题
D-最短Hamilton路径_0x01 基本算法-位运算
朴素算法：枚举全排列，求最小 ：O ( n * n ! )
二进制状态压缩：F [ i , j ]为在i状态下，终点为j的最短路径。其中 i 为二进制数存储bool数组，第k个点已经过，则第k位为1。
考虑状态转移：则枚举“中转点”，找最短的路径。
f[i][k] = min(f[i][k], f[i xor 1 << k][j] + a[j][k]);