基础模板(Basic)
位运算

1. 与(&)运算

(1)运算法则

两个二进制数进行 与(&)运算,如果对应位都为 $1$ 则结果为 $1$,否则为 $0$。

(2)技巧及用途

与运算常常用于二进制下的取位操作。想要知道二进制下的某位是否是 $1$,就 & 上这个位数对应的十进制数。假如返回的是这个十进制数本身,则这个位的确是 $1$,反之就是 $0$。

比如:

我们要取第 $3$ 位是否为 $1$,我们只需要与 & 上 $3$(二进制表示为 100)对应的二进制数 $4$,如果返回值为 $4$,就代表第三位为 $1$,反之就是 $0$。

最常用的是取二进制下的最末位,即 $a \ \& \ 1$。这样的技巧可以用于判断奇偶,根据二进制常识,尾数为 $1$ 则为奇数,反之为偶数。

2. 或(|)运算

(1)运算法则

两个二进制数进行或(|)运算,如果对应位有一个为 $1$,结果就为 $1$。只有在两个数的对应位置都是 $0$ 的时候,结果才为 $0$。

(2)技巧及用途

或运算常用于二进制特定位的赋值。想把哪个位强行变成 $1$,就用这个数 | 上这个位数对应的二进制数。

还是上面那个例子,我们想让 00000 的第三位变成 $1$。即十进制变 $4$,我们直接 | 上 $4$ 就可以。

当然,不同于 & 运算,我们很少用 | 运算进行任意位赋值。通常来讲,我们只使用 $a|1$ 把 $a$ 的最后一位强行变成 $1$,其实质意义是把原数加一。或者使用 $a|1-1$ 再把它变为 $0$。这个技巧通常用于把它变成它最接近的偶数。

3. 异或(^)运算

运算法则

两个二进制数进行异或(^)运算,如果对应位相同,不管是 $0$ 或者是 $1$,都返回 $1$,反之返回 $0$.

4. 非(~)运算

运算法则

把给定二进制数全部取反。

5. 左移(<<)运算

(1)运算法则

a<<b 表示把 $a$ 的二进制位向左移动 $b$ 位,低位用 $0$ 补上。

(2)技巧及用途

根据二进制的常识,我们会发现,二进制第 $k$ 位上的数就等于 $2k$。(从 $0$ 开始计位)

比如,二进制下的 100 就是 $4$。

所以我们发现,左移运算 a<<b 的实质就是 $a \times 2b$。

左移运算最常用的技巧就是用来代替 $\times 2$ 的整数次幂的乘法运算。因为我们普遍认为,位运算是要比四则运算加减乘除及模运算更快一些的运算。

6. 右移(>>)运算

(1)运算法则

a>>b就是把a的二进制位向右移动b位,溢出的舍去。

(2)技巧及用途

类比于左移运算,我们发现右移运算就是把a除以2的整数次幂。这就是右移运算的用途——优化除法运算。

这里需要特殊说明的是,右移算法可以用在数学知识中的求最大公约数的程序块上。因为mod运算的效率慢的出奇,所以我们可以用右移运算来进行除以2的操作。据说可以提高百分之60的效率。

常用操作

1. 获得第 $i$ 位的数字:(a>>i)&1 或者 a&(1<<i)

很好理解,我们知道可以用&1来提取最后一位的数,那么我们现在要提取第i位数,就直接把第i位数变成最后一位即可(直接右移)。或者,我们可以直接&上1左移i位,也能达到我们的目的。

2. 设置第 $i$ 位为 $1$:a=a|(1<<i)

我们知道强制赋值用|运算,所以就直接强制|上第i位即可。

3. 设置第 $i$ 位为 $0$:a=a&(~(1<<i))

这里比较难以理解。其实很简单,我们知道非~运算是按位取反,(1<<i) 非一下就变成了第i为是0,其它全是1的二进制串。这样再一与原数进行&运算,原数的第i位无论是什么都会变成0,而其他位不会改变(实在不明白的可以用纸笔进行推演)。

4. 把第 $i$ 位取反:a=a^(1<<i)

1左移i位之后再进行异或,我们就会发现,如果原数第i位是0,一异或就变成1,否则变成0。

5. 取出一个数的最后一个 $1$:a&(-a)

学过树状数组的同学会发现,这就是树状数组的lowbit。事实上,这和树状数组的原理是一样的。我想,不需要我多解释。