位运算¶
算数位运算¶
二进制意义：
将二进制数的每一位看作旗帜
与：将二进制数的某一位设为0，可用于位的提取
或：将二进制数的某一位设为1，可用于大量布尔变量的保存
异或：1. \(x \oplus x=0\) 2.对二进制数的某一位切换，可用于操作二进制数
补码¶
定义：
设计原理(a,b为n位二进制数)：
1.加减法统一：\(a-b=a+(-b)\)，用加法表示减法
2.自然溢出：若\(a+b\geqslant2^n\)，则\(a+b=a+b-2^n\)
(溢出且至多溢出一次(\(a+b-2^n<2(2^n-1)-2^n<2^n\)))
推导：\(-a=0-(a)\overset{①}{=}2^n+0-(a)\overset{②}{=}(2^n-1+1)-(a)=(2^n-1-a)+1\overset{③}{=}\sim a+1(其中a>0)\)
①由加法的自然溢出，减法可向第\(n+1\)位（溢出位）借位至多1次
②n位二进制数能表示的最大的数为\(\overline {11…1}_{(2)}=2^n-1\)，故将\(2^n\)拆为\(2^n-1+1\)，进而调整运算次序
③\(\sim a\)与\(a\)每一位各为0和1，故\(a+\sim a=\overline {11…1}_{(2)}=2^n-1\)，即\(2^n-1-a=\sim a\)
注：推导过程中未需考虑符号位，因为符号位为负数的原码表示下赋予的意义，在利用正数推导补码时无需考虑
推广：负数补码表示转换为原码表示：利用\(0-(-a)=a(a>0)\)，将负号提出
应用：int数组无穷大初始化
int变量的最大值：\(\overline{01111111\ 11111111\ 11111111\ 11111111}_{(2)}=0x7F\ FF\ FF\ FF\)
\((\overline{0111\ 1111}_{(2)}=0x7F)\)
\(memset(a, val, sizeof(a))\)语句：将\(val(0x00 \sim 0xFF)\)(8 bit)填充到数组a的每一个字节(byte)上
因此，\(0x7F7F7F7F\)为\(memset\)语句能初始化出的最大数值
技巧：选择\(0x3F3F3F3F\)做无穷大，使得\(2INF<INT\_MAX\)
移位运算¶
算数意义：
左移：\(1\ll n=2^n,n\ll 1=2n\)(高位越界舍弃)
略证：
对于正数，\(S\ll1=\sum\limits_{n}2^{n+1}a_{n}=2\sum\limits_{n}2^{n}a_{n}=2S(S>0)\)
对于负数，易证\((a\pm b)\ll1=(a\ll1)\pm (b\ll1)\)(先进退位=先左移后进退位，第0位不影响高位进退位)
设该n位负数为\(-S(S>0)\)，则\((-S)\ll1=(2^n-S)\ll1=2^{n+1}-2S(*)\)
而\(2^{n+1}-2S\geqslant2^{n+1}-2(2^{n-1}-1)>2^n\)(正数符号位为0)
故发生且仅发生一次溢出，\((*)=2^{n+1}-2S-2^n=2^n-2S=-2S\)
进一步地，若\(-2S\)能够被表达（即本身未溢出），则\(-2S<0\)，即符号位为1，那么\(2^n-2S\geqslant2^{n-1}\)，即\(S\leqslant2^{n-2}\)
那么\(-S=2^{n}-S\geqslant2^{n-1}+2^{n-2}\)，即该负数应满足第n-2位为1，才能保证左移后不发生溢出
反过来，若第n-2位为0，左移后符号位变为0，溢出为正数
算数右移：\(n\gg 1=\lfloor \dfrac {n}{2.0}\rfloor\)(高位填符号位)
c++整数除法向0取整
略证：
若\(S=2n\)，则\(S\gg1=(n\ll1)\gg1=n=\dfrac{S}{2}\)
若\(S=2n+1\)，则\(S\gg1=(n\ll1+1)\gg1=n=\dfrac{S-1}{2}=\lfloor \dfrac {S}{2.0}\rfloor\)
逻辑右移：高位填0
例1 a^b
思路：二进制拆分
对指数b进行二进制拆分，即\(a^b=a^{\sum\limits_{n}2^{n}b_{n}}=\prod\limits_{n}a^{2^nb_n}=\prod\limits_{b_n=1}a^{2^n}\)
(拆分：化整为零，化幂为积，实现降次)
利用循环生成\(a^{2i}\)，即\(a^{2i}=(a^{i})^2\)
判断\(b\)的二进制表示每一位是否为1：将\(b\)不断右移，利用\(b\)&1取出第0位
时间复杂度估计：
\(b\)的位数不超过\(\lceil log_2(b+1)\rceil\)(n位二进制数最大为\(\overline{11…1}_{(2)}=2^n-1\))，故复杂度为\(O(log_2b)\)
实现：
int a, b, p;
cin >> a >> b >> p;
int ans = 1 % p; // 不写ans=1:防止b=0,p=1的情况，此时无法进入循环，而ans=0
for (; b; b >>= 1) { // 遍历b二进制表示的每一位
if (b & 1) ans = (long long)ans * a % p; // 不写*=:方便取模
a = (long long)a * a % p; // 计算时变量类型与保存结果的变量类型无关，需强制类型转换
}
cout << ans << endl;
例264位整数乘法
思路1：二进制拆分
对乘数b进行二进制拆分，即\(a*b=a\sum \limits_{n}2^nb_n=\sum \limits _{n}2^nab_n=\sum \limits_{b_n=1}2^na\)（化积为和）
其中\(2^na=2^{n-1}a*2\)
时间复杂度：\(O(log_2 b)\)
实现：
long long a, b, p;
cin >> a >> b >> p;
long long ans = 0;
for (; b; b >>= 1) {
if (b & 1) ans = (ans + a) % p;
a = a * 2 % p;
}
cout << ans << endl;
思路2：数论
易知：\(n\%p=n-\lfloor\dfrac{n}{p}\rfloor*p\)(余数定义),\((a*b)\%p=(a\%p)*(b\%p)\)(对a,b做带余除法，代入)
故\((a*b)\%p=a*b-\lfloor\dfrac{a*b}{p}\rfloor*p\ (*)\)
又\((*)<p\),可使两项自然溢出而得到正确结果
实现：
long long a, b, p;
cin>>a>>b>>p;
a %= p, b %= p; // 2.
long long c = (long double)a * b / p; // 1.
long long ans = a * b - c * p;
if (ans < 0) ans += p;
cout << ans << endl;
1.此处有溢出的可能性。该过程可以表示为：\(a*b\xrightarrow{}溢出\xrightarrow{}除以p\xrightarrow{}类型转换\)，下面在\(a*b\)溢出为负数的前提下考察这几个步骤：
溢出过程：将\(a*b\)作整体考虑，\(a*b\)在补码意义下将表示负数。以3位补码为例，按二进制由小到大表示的数依次为：\(0,1,2,3,-4,-3,-2,-1\)，即构成\(-4,-3,-2,-1,0,1,2,3\)的循环，故自然溢出并未改变数字的相对大小。
除法过程：尽管我们不清楚除法的底层实现，但从其算数效果来看，符号位将影响计算方式(类比算数右移)，具体表现为负数除以正数，结果仍为负数。
类型转换：将实数转换为整数的底层实现是去掉小数位，而去掉小数位对正数的影响是缩小，但对负数而言是放大(向0取整)，这是导致相对大小发生变化的根源。
由此可见，由于类型转换向0取整的特性，导致实际计算结果与我们期望的向下取整有了出入。有两条解决思路：一是将a,b的变量类型指定为unsigned；二是对计算结果进行讨论，若结果为负，则补一个p:
\(n-\lceil\dfrac{n}{p}\rceil*p=n-(\lfloor\dfrac{n}{p}\rfloor+1)*p=n-\lfloor\dfrac{n}{p}\rfloor*p-p\)
2.由\((a*b)\%p=(a\%p)*(b\%p)\)知，通过分别取模，在缩小数据范围的同时保证结果的正确性：取模后\(a,b<p\),\(a*b<p^2\);若此处不取模，则无法保证\(a*b<p^2\)
3.处利用long double科学计数法的特性，将我们需要的精度保存下来；而若不对a,b进行范围限制，则\(a*b\)位数过多，会丢失必要精度，导致自然溢出了不该溢出的位数从而得到错误结果。
二进制状态压缩¶
定义：用m位二进制数存储长度为m的\(bool\)数组
基本元素：
\(\ll\)：用于\(\overline{10…0}_{(2)}\)的生成 \(\gg\)：用于数位的搬动
&：1.将数位置为0 2.将数位取出 |：1.将数位置为1 2.将数位放入 \(\oplus\)：将数位切换
\(\sim\)：将数位取反
1：用于操作的数位 -1：用于\(\overline{11…1}_{(2)}\)的生成
操作：(n的处理) 操作符 蒙版
取第k位：\((n\gg k)\)&\(1\)
取第0-k-1位：\(n\)&\((-1+(1\ll k))\)
利用-1生成\(\overline{11…1}_{(2)}\),再利用第k位的1使第\(k \sim n\)位进位，第n位自然溢出，构成局部蒙版
取反第k位：\(n\oplus(1\ll k)\)
第k位 置1：\(n|(1\ll k)\)
第k位 置0：\(n\)&\((\sim (1\ll k))\)
利用&进行置0，需要\(\overline{11…0…1}_{(2)}\)的模板，可将\(\overline{11…1}_{(2)}\)位于第k位的1减去，即
\(-1-(1\ll k)=\sim (1\ll k)\)
例3最短Hamilton路径
思路1：暴搜
我们可以枚举每一种合法路径，计算出路径长度的最小值。
时间复杂度估计：
对于n个点，从0号点出发，第一次有n-1种选择，第二次n-2种，由此类推，共\((n-1)!\)种路径；对于每条路径上的每一个点，需要花费\(O(1)\)的时间叠加边权，而每条路径都有\((n-1)\)条边，故时间复杂度为\(O(n*n!)\)
思路2：状压DP
思路1复杂度过大的根本原因是我们记录了冗余数据：点的访问顺序。由于我们只需求解最短路径，所以无需关心具体走法，可以设置简化的状态，降低时间复杂度。
首先，由于我们不需要考虑点的访问顺序，我们可以仅记录所有点的访问状态，又由于每个点仅有访问和不访问两种状态，故可以使用二进制进行状态压缩。由于答案对访问的末端点进行了要求，故我们需要将末端点编号加入状态中，以区分访问状态相同但末端点不同的两个状态。
由此，我们设计出如下状态：
\(f[S][k]\)：访问状态为S且末端点位于k的最短路径长度，边界为\(f[1][0]=0\)
接着考虑状态转移。从状态本身出发，我们忽略访问顺序，对于状态\(f[S][k]\)的转移，可以理解为：
●●●●●●|● \(\xrightarrow{}\) ●●●●●o \(\xrightarrow{}\) min{●'●●●●o|●' + w(●',o)}
写作数学表达式即
\(f[S][k]=\min\limits_{((S\oplus(1\ll k))\gg i)\&1}\{f[S\oplus(1\ll k)][i]+w[i,k]\}\)
由于确保k点一定被经过，故使用\(\oplus\)将1置为0
时间复杂度估计：
状态空间\(2^n*n\),转移花费\(O(n)\)，故时间复杂度为\(O(2^n*n^2)\)
实现：
memset(f, 0x3f, sizeof(f)); // 1.
f[1][0] = 0;
for (int S = 1; S < (1 << n); S++) // 2.
for (int k = 0; k < n; k++)
if ((S >> k) & 1)
for (int i = 0; i < n; i++)
if (((S ^ (1 << k)) >> i) & 1)
f[S][k] = min(f[S ^ (1 << k)][i] + w[i][k], f[S][k]);
细节：
1.由于状态转移方程的策略为取min,为防止初值对结果的干扰，将f初始化为无穷大
2.状态转移方程等式左边的值从等式右边获得，故要求等式右边先于等式左边计算；观察转移方程，不难发现等式右边\(S \oplus (1\ll k)\)始终小于等式左边的S，故要求S始终按照递增的顺序进行枚举，所以将S放在外层循环保证S始终递增
例4起床困难综合症
思路：模拟
不难发现三种按位操作的独立性：对每一位进行&、|、\(\oplus\)操作后，均不对高位产生影响。
在这基础上，我们只需要对初始攻击力二进制表示的每一位进行讨论，便能得到最大的伤害。一般地，若能证明某数的各个数位互相独立，就不用考虑各个数位各种情况的组合，时间复杂度将由\(O(n)\)优化至\(O(logn)\).
故时间复杂度为\(O(nlog_2m)\)
实现：
bool calc(int pos, bool bit) {
for (int i = 0; i < n; i++) {
bool x = ((t[i] >> pos) & 1);
if (ops[i] == 0)
bit &= x;
else if (ops[i] == 1)
bit |= x;
else
bit ^= x;
}
return bit;
}
int main() {
string op;
cin >> n >> m;
for (int i = 0; i < n; i++) {
cin >> op >> t[i];
if (op == "AND")
ops[i] = 0;
else if (op == "OR")
ops[i] = 1;
else
ops[i] = 2;
}
for (int pos = 29; pos >= 0; pos--) { // 1.
bool res0 = calc(pos, 0), res1 = calc(pos, 1);
if (m >= (1 << pos) && res1 > res0) // 2.
m -= (1 << pos), ans += (res1 << pos);
else
ans += (res0 << pos);
}
cout << ans << endl;
return 0;
}
细节：
1.此处采用贪心策略，先填高位，后填低位：由于高位带来的贡献大于低位，尽可能的在高位处多填1，使结果最大化；pos从29开始递减，是因为n最大为\(10^9\),二进制表示最多30位，最高位最大为第29位。
2.此处采用贪心策略，若不是一定填1，则选择填0：若高位填0或1带来的结果一致，则优先选择填0，为低位选择留出更多空间。
注：此时初始攻击力的选择可能有多解(例如最后一层AND 0)，而最大伤害值的解唯一：若能填1，则一定填1；若不能填1，则填0。
成对变换¶
利用\(\oplus\)位切换的性质，对n的第0位进行切换，形成偶数加一，奇数减一的效果。
lowbit运算¶
定义：非负整数n二进制表示下最低位1及后边所有0构成的数值。
推导：差异化
利用定义给出的\(\overline{…10…0}_{(2)}\)中的1，使1前和1后发生不同的变化。
差异化根源：进位
思路：
将n取反，加一则产生进位，由于原位置的1取反后化为0，将进位截断，故高于1的位不改变取反状态。此时该数与原数低于1的位完全相同，高于1的位完全相反。再与原数做&，即可取出lowbit.
写作数学表达式：
\(lowbit(n)=n\&(\sim n+1)=n\&(-1-n+1)=n\&(-n)\)
应用：取出二进制中所有的1
将n不断减去lowbit(n),不断移除此时最低为的1
1的位数为\(log_2lowbit(n)\),利用哈希将对数表准备好
GCC内置相关函数：
int __builtin_ctz(unsigned int x) 返回x二进制表示下最低位1后有多少0
int __builtin_popcount(unsigned int x) 返回x二进制表示下有多少位为1