位运算

之前那个写的太垃圾了……今天我们重写一回。

中考结束之后就可以随心所欲地学 OI 了，先复习一下吧……

关于把所有人都取关了这件事……我被机惨了，我也懒得再关回来了。（喂我可不想点上百个关注啊！）

这个玩意写的时间比较长，复习一共开始没多久，写的慢一点对我也好……（行，就是我拖更）

行，正题开始。

温馨提示：本片博文含有大量的 $\LaTeX$，我尽量让大家看得舒服点，如果哪里排版炸掉了直接评论区告诉我我尽力改掉。

如有学术错误，请毫不留情地在评论区指正，本人会仔细思考后采取措施，谢谢大家！

我们先解释一下计算机中数的存储方式吧。

我们常说的与，或，非，异或这些逻辑运算的东西同样可以用于二进制的这些东西进行运算。至于这些东西怎么运算的……我觉得大家应该都会就不说了，反正随便个人都爆踩我这种蒟蒻。

在一个二进制整数中，我们定义其有 $n$ 位，最低位为 0，最高位为 $n-1$。

我们熟知的 int 和 unsigned int 都是 32 位整数（注意，C++ 里之规定这俩玩意位数不小于 16 位，但是多数现代计算机上都是拿 32 位算的，注意把这两个东西与 32 位整数相等是不严谨的）。

的最高位是符号位，0 表示非负数 1 表示负数，但是 ```unsigned int``` 没有这一位（下文我们统一将 ```unsigned int``` 简写为 ```uint```），也就是说，```uint``` 这东西把它存负数的那一堆全用来存了正数！

现在知道为什么 ```uint``` 比 ```int``` 在正数上能多存一倍了吧，人家二进制比你多一位！

当然，只要别闲的拿它存负数什么都好说……

还有个重要的东西叫**补码**。

补码如下：

```uint``` 的补码就是直接换成 32 位的二进制数。

```int``` 当最高位为 $0$ 时直接看成 32 位的二进制数。

如果你把 ```int``` 最高位给它取反，假如原二进制数是 $x$，它会变成 $-1-x$。

不难发现，如果你把两个数加减运算的话，就等价于在二进制补码下进行**最高位不进位**的二进制加减。如果算术溢出的话会直接给你按 $2^{32}$ 给你取模，这也是为什么你会爆 ```int``` 的原因。直接给你加成负数（）

现在问题来了，写代码的时候如果我们想要表示一个 ```int```，拿二进制写你得写个 32 位，直接累死。换十进制又表示不出补码的每一位（计算机可是拿这东西运算的喂！），因此我们用 8 位十六进制数来表示一个数。

首先你要让计算机知道你写了个十六进制的数，你需要一个前缀：

```0x```

注意，这个玩意是声明十六进制用的，和数值**毫无关系**！

接下来，用十六进制来表示你要的数（十六进制大家应该都会）。

比如一个非常好用的数：

```0x3f3f3f3f```

这个值通常被我们拿来当无穷大来用，聪明的同学一定要问了：

“那我们为什么不直接拿 ```0x7fffffff``` 呢？这东西是 ```int``` 能表示的最大整数！”

很简单，随便一加就给你溢出了……你不会拿个负数当无穷大吧……

而且，C++ 里边有个东西叫 ```memset```，它按**字节**给你赋值，也就是按 ```0x00~0xff``` 给你每一个**字节**赋值，当然你要是 ```0xff``` 会溢出的，而一个 ```int``` 占用 4 个**字节**，```memset``` 每次赋值一个**字节**，这也解释了为什么 ```memset``` 只能赋值出每 8 **位**都相同的 ```int```。（注意，位不等于字节！）

因此你可以直接这样初始化一个数组：

```memset(a, 0x3f, sizeof(a))```

这样里边的每一个数都会变成：

```0x3f3f3f3f```

这是 ```0x3f3f3f3f``` 的一个好处，每八位都相同，还有一个实用的地方是把它乘以 2 也不会超过 ```int``` 能表示的最大整数，完美规避过算术溢出。

是不是很简单呢？

这样，你在贪心和 DP 的时候就快乐多了！

好吧其实就算你没看懂上边这一堆……就当我教了你怎么初始化一个无穷大的数组得了，虽说授人以鱼不如授人以渔，但是死活学不会渔我也没救。

现在，你大致弄明白了计算机中数的存储方式！

下面我们说一说位移运算。

左移：

在二进制下将数整体向左移动，低位用 0 填上，高位越界之后舍弃掉。

根据二进制数的表示方法，不难发现：

$(n \ll 1) = 2n, (1 \ll n) = 2^n$

为啥我加了括号……位运算不加括号真的容易暴毙……所以位运算就加括号吧，免得先判断再运算了。

右移分为两种：算术右移与逻辑右移。

算术右移：在二进制补码下把所有数字向右移，低位越界后舍弃，高位用**符号位**补上。

不难发现，$(n \gg 1) = \left\lfloor\dfrac{n}{2.0}\right\rfloor$


有趣的是，“整数 / 2”这东西在 C++ 中是以除以二向零取整来实现的。

逻辑右移：与算术右移的区别在于，最高位拿 0 来补充。

C++ 中没有规定到底是用逻辑右移还是算术右移，这事编译器说了算。一般编译器都按算术右移来，所以我们一般默认右移是按算术右移操作。

现在我们位运算学的差不多了，让我们来看看位运算能做些什么吧！

### 快速幂

我们有时需要求 $a$ 的 $b$ 次方的值（有时取个模），不难发现如果一个一个乘的话时间复杂度是 $\mathcal{O}(b)$，容易发现如果 $b$ 足够大我们是会 TLE 的，因此需要降低复杂度。

我们都知道，每一个正整数都可以唯一表示为若干指数不重复的 2 的次幂的和，如果 $b$ 在二进制下有 $n$ 位，其中第 $i$ 位的数字为 $c_i$，可以证明：

$b = c_{n-1}2^{n-1}+c_{n-2}2^{n-2}+\dots+c_02^0$

然后你要给 $a$ 来个 $b$ 次方：

$a^b = a^{c_{n-1}2^{n-1}} * a^{c_{n-2}2^{n-2}}*\dots*a^{c_02^0}$

你还知道 $n = \left\lceil\log_2(b+1)\right\rceil$，你也知道一个基本的数学原理：

$a^{2^i} = (a^{2^{i-1}})^2$

我们可以容易地通过 $n$ 次递推弄出每一个乘积项，当 $c_i = 1$ 时我们将该乘积项累积到答案中，将 $b\ \&\ 1$ 可以得到最低位是否为 1，然后右移舍弃此位看下一个，这样我们通过遍历二进制下的数位得出了解，时间复杂度降为了 $\mathcal{O}(log\ b)$ （别问我为什么不写底数，换底公式自己去看）。

那我们写写看看：

```cpp
int power(int a, int b) {
    int ans = 1; // 众所周知，乘法答案初始化成 1
    while(b) { // 遍历 b，直到把 b 右移完
        if(b & 1 == 1) ans = ans * a; // 若此位上数是 1，则此位需要累计入答案中（毕竟你乘个 1 跟没乘一样啊！）
        a *= a; // 更新此时的 a
        b >>= 1;
    }
    return ans;
}

解释一下：这里 $a$ 存储的是 $a^{2^i}$。

我都写了这么多注释了，你应该是能看懂的。

64 位整数乘法

题目

什么？！64 位！还是乘法！这不得爆 long long ！

我知道你要大声地喊出：我要高精！

好吧，今天让你见识一下怎么不用高精来处理！

众所周知，long long 是 64 位的，能比 int 多存好多好多，但是这么大的数也是爆掉了，我们得换个思路。

有两种方法解决这个问题：

1. 还记得快速幂吗？

我们依旧将 $b$ 拿二进制来表示，和之前一样就不写了，因此 $a * b = a^{c_{n-1}2^{n-1}} + a^{c_{n-2}2^{n-2}}+\dots+a^{c_02^0}$

注意一下这个式子和之前那个的区别！

我们也知道：$a * 2^i = (a * 2^{i-1}) * 2$，因此我们可以每乘一次都取模一下 $p$，不会超出 64 位整数的极限，这样这道题就跟之前没什么区别了。

写一下：

#define ll long long


ll work(ll a, ll b, ll p) {
    ll ans = 0;
    while(b) {
        if(b & 1) ans = (ans + a) % p;
        b >>= 1, a = (a + a) % p;
    }
    return ans % p;
}

2. 利用除法性质

容易知道：$a * b \mod p = a * b - \left\lfloor\dfrac{a * b}{p}\right\rfloor * p$，我们记录 $c = \left\lfloor\dfrac{a * b}{p}\right\rfloor$。

现在问题转化为：如何求 $c$ 呢？不妨想想用浮点数直接算 $c$，当精度撑不住了它会自动舍弃低位，因此小数点后面的东西是不精确的，利用这一特性可以向下取整。一种数据类型叫做 long double，十进制下它可以抗 18~19 位的数据，这样它就可以保下整数部分的精确值 $c$，然后强制换成 unsigned long long 型直接舍去小数点后东西。如果 $a * b$ 恰好被 $p$ 整除，处于精度误差，$c$ 可能比实际小 1，但是取模意义下不影响结果正确性。

现在有了 $c$，下面只需要算出 $a * b - c * p$ 就可以了，因为上式实际上就是 $a * b \mod p$，所以 $a * b - c * p \leqslant p < 2^{64}$，所以我们直接给取一下 $2^{64}$ 的模，而 unsigned long long 的溢出恰好满足此要求，因此用 unsigned long long 算 $x = a * b$ 与 $y = c * p$，然后用 long long 计算 $(x \mod p - y \mod p) \mod 2^{64}$，大功告成，并且时间复杂度为 $\mathcal{O}(1)$，比上面的方法快得多。

写一下：

#define ll long long
#define ld long double
#define ull unsigned long long

ull work(ull a, ull b, ull p) {
    a %= p, b %= p; // 如果 a，b 一定在 0~p 之间，不用写这一步
    ull c = (ld) a * b / p;
    ull x = a * b, y = c * p;
    ll ans = (ll)(x % p) - (ll)(y % p);
    if(ans < 0) ans += p; // 防止弄出负数来
    return ans;
}

二进制状态压缩

我们一般简称状压。

这东西是指将一个长度为 $n$ 的 bool 数组用一个 $n$ 位二进制数来表示。利用下面位运算操作可以实现原 bool 数组中对应的下标元素的存取。

(n >> k) & 1 取出整数 n 在二进制下的第 k 位
n & ((1 << k) -1) 取出整数 n 在二进制下的第 0~k-1 位
n xor (1 << k) 把整数 n 在二进制表示下的第 k 位取反
n | (1 << k) 把整数 n 在二进制表示下的第 k 位赋值为 1

n & (~(1 << k)) 把整数 n 在二进制表示下的第 k 位赋值 0

这种方法运算简便，并且节省了程序运行的空间和时间，如果 $n$ 不是很大，直接一个整数即可存储，反之可以用若干整数类型存储，或者直接 bitset。

来个例题：

题目

这道题需要一点图论知识，如有需要请去我博客中慢慢翻出来吧。

容易想到朴素做法：枚举每个点的全排列，然后计算路径长取最小值，时间复杂度也就区区的 $\mathcal{O}(n * n!)$ 而已，如果你运气足够足够足够足够足够……（以下省略 $n$ 个足够）好，也是可以跑过去的！

但是我们并不是欧皇，那怎么办呢？

看到最值了，而且明显贪心不了，数论也没辙，只能 DP 了。

任意时刻，如果表示哪些点已经经过，哪些没有？我们很明显需要一个 $n$ 位进制数来解决问题，如果其第 $i$ 位为 1 则来过，反之没有来过。同时我们还需要知道现在所处的位置，因此可以设计状态：

$dp[i][j]$，表示在 $j$ 点上，其中第 $i$ 点是否被经过，此时的最短路径。

初始化一下，在起点时，$dp[1][0] = 0$ ，你只经过了 0 点，处于起点 0，此时路径长也为 0。其余值我们设为无穷大，我们的目标是：

$dp[(1 \ll n) - 1][n-1]$，即经过所有点后在终点时的最短路径。

可以找到状态转移方程：

$dp[i][j] = \min{dp[i\ \operatorname{xor}\ (1 \ll j)][k] + weight(k, j)}$，$0\leqslant k < n$ 并且 $((i \gg j) & 1) = 1$。

然后，我们写写看看。

int dp[1 << 20][25];

int work(int n, int w[25][25]) {
    memset(dp, 0x3f, sizeof(dp));
    dp[1][0] = false;

    for(int i=1; i<(1 << n); i++)
        for(int j=0; j<n; j++)
            if(i >> j & 1)
                for(int k=0; k<n; k++)
                    if((i^1<<j) >> k & 1)
                        dp[i][j] = min(dp[i][j], dp[i^1 << j][k] + w[k][j]);
    
    return dp[(1 << n) - 1][n - 1];
}

再来一个：https://www.acwing.com/problem/content/1000/

当你们看到这题的时候心情估计是爆炸的。

没关系，我第一眼也是这样的。

考虑下位运算的特性：在二进制表示下不进位。

这就意味着：你最终的答案上二进制对应的位只和你选择的数的那一位有关！

既然如此，那我们直接去枚举每一位上填 1 好还是填 0 更好就可以了！

比如说，这一位要填 1，要满足两个条件：

1. 这一位填上 1 之后形成的数不能超过 $m$。
2. 这一位填 1 要比填 0 好。

如果不满足上述条件中的任何一个，我们只得填 0。

因此，我们可以写出如下代码：

pair <string, int> d[100005];

int work(int bit, int now) {
	for(int i=0; i<n; i++) {
		int x = d[i].second >> bit & 1;
		if(d[i].first == "AND") now &= x;
		else if(d[i].first == "OR") now |= x;
		else now ^= x;
	}
	
	return now;
}

int main() {
	scanf("%d%d", &n, &m);
	for(int i=0; i<n; i++) {
		string s;
		int x;
		cin >> s;
		scanf("%d", &x);
		
		d[i] = make_pair(s, x);
	}
	
	int val = 0, ans = 0;
	for(int bit=29; bit>=0; bit--) {
		int res0 = work(bit, 0);
		int res1 = work(bit, 1);
		
		if(val + (1 << bit) <= m && res0 < res1)
			val += 1 << bit, ans += res1 << bit;
		else ans += res0 << bit;
	}
	
	printf("%d", ans);
	return 0;
}

成对变换

不难发现：

对于任意整数 $n$：

$n$ 为偶数，则 $n \operatorname{xor} 1 = n + 1$，

$n$ 为奇数，则 $n \operatorname{xor} 1 = n - 1$。

为什么呢？因为在二进制下，一个数为奇数则最低位为 1，偶数则为 0。

所以，0 和 1，2 和 3， 4 和 5 ……构成…“成对变换”。

这个性质常被用于邻接表中边集的存储。

lowbit 运算

我们定义：

$\operatorname{lowbit}(n)$ 表示非负整数 $n$ 在二进制表示下“最低位的 1 及其后边所有的 0” 构成的数值。

下面我们来推推 $\operatorname{lowbit}$ 的公式。

设最低位的 1 在 $k$ 位上

为了实现 $\operatorname{lowbit}$ 的运算，我们需要将 $n$ 取反，让 $k$ 此时为 0，然后给它加个 1，此时 $k$ 会变回 1，后边皆为 0。

上面这波取反加 1， $n$ 的第 $k+1$ 位到最高位与原来都相反，因此如果你来个这个操作：

$n\ &\ (\sim n+1)$

这样，只会有第 $k$ 位是 1！

我们也知道，补码下将 $n$ 取反就会变成 $-1-n$

因此可以推出：

$\operatorname{lowbit}(n) = n\ &\ (\sim n+1) = n\ &\ (-n)$

那么 $\operatorname{lowbit}$ 能用来干什么呢？

我们可以用这个东西搭配 $\operatorname{Hash}$ 来找出整数二进制表示下所有是 1 的位，时间复杂度与 1 的个数同级。

怎么做呢？

我们不断把 $n$ 赋值成 $n-\operatorname{lowbit}(n)$，一直到 $n = 0$。取出我们减去的这两个数，然后取它们的对数，然后可以得知 $n$ 的第几位是 1 了。

除此之外，$\operatorname{lowbit}$ 在树状数组中也是基础的运算。