一些位运算技巧
x + ~x = -1
(因为自身加上对自身取反的话,那么二进制所有位都变成 1 了,按补码规则表示为 -1)
于是我们有 -x = ~x + 1
设置第 k
位:y = x | (1 << k)
清除第 k
位:y = x & ~(1 << k)
切换第 k
位:y = x ^ (1 << k)
c123x = x ^ y; // 此时 x 相当于把原来的两个数字合在了一起
y = x ^ y; // 合在一起之后异或 y 就相当于把 y 消掉,取出 x
x = x ^ y; // 同上
不过这个技巧未必性能更优。因为上面三个操作之间有严重的数据依赖,导致指令的并行性很差。对比传统的引入临时变量来交换:
c
123temp = x; x = y; y = temp;
CPU 可以同时取出 x
和 y
然后并行地执行前两个操作。朴素的做法指令的并行性更好。
r = min(x, y) = y ^ ((x ^ y) & -(x < y))
如果 x < y
,那么 -(x < y)
为 -1,二进制下全 1,使得最后结果为 (y ^ (x ^ y)) = x
。而如果 x >= y
的话后面那堆东西就为 0。
相比于朴素做法,直接通过判断取 min 的话,分支预测错误的代价比较大。不过也不好说,因为编译器应该会使用条件传送吧()
c123z = x + y;
r = z - (n & -(z >= n));
// 第二行等价于 r = (z < n) ? z : z - n; 这里使用了类似取 min 的技巧
其大概思想就是将 n - 1
中的所有二进制位都向后覆盖,最后低位都是 1
,再加一个 1
就变为 2 的幂次了:
其中 -1
是为了处理 n
已经是 2 的幂次的情况。
r = x & (-x);
树状数组学过,这里再复习一下:
这里的 -x
为 ~x + 1
,其中对 x
取反之后,原来的 lowbit 就变为 0,而 lowbit 之前的位全变为了 1,此时我们直接再 + 1
,lowbit 之前的位全部进 1,使得 lowbit
又变为 1
了,而 lowbit
之后的位仍然不变,这使得再按位与的时候后面都是 0。
这里的取 log 的底数是 2,也就是我们想知道一个 2 的幂次的指数。
原理是 deBruijn 序列。这种序列满足,序列中任意长度为 的区间内的位表示的数字都是不同的,比如:
其中的 00011101
就是一个 deBruijn 序列。我们可以得到一个 convert
数组,记录一个二进制下的三位数在上面的第几行出现。
然后我们考虑,如果我们把这个 deBruijn 序列左移 位,然后取出高 位,就相当于拿到一个特征值,然后此时这个 就对应于上图中左边的数字。如果我们不知道 ,仅凭特征值和 convert
数组仍然可以得知这个 。
回到最开始的问题,对于 2 的幂次 ,我们直接让 deBruijn 乘上这个 ,就相当于进行了左移。
后面我查了一下如何构造 deBruijn 序列,可以使用求欧拉回路的算法。比如我们有如下的图:
一种欧拉回路是 01011100
(从点 00
出发)。再验证一下,确实是 deBruijn 序列。
我们现在想要通过一个长度为 的区间,在 deBruijn 序列上滑动,得到所有的三位二进制数。当区间向右滑动时,低两位就变成了高两位,得到的新的数字的低两位数字发生了变化。我们将低两位看成是一个状态,对应于图上的点。在当前状态下再追加一个二进制位看成是状态的转移,对应于图上的有向边。然后在图上,点和连出去的边组合在一起就是一个三位的二进制数。如果存在一个回路能把所有的边覆盖,我们也就相当于覆盖了所有的数字,而这就是欧拉回路。
朴素的做法就是直接逐位枚举统计。
我们还可以多个位多个位地统计:
理论上我们一次统计的位数越多,循环次数越少,速度越快。但是还需要考虑到缓存的影响,count
数组越大,其缓存的利用率越小,可能反而增加时间。
还有一种分治的算法:
大概思想就是,两个两个地计算 1 的数量,然后再四个四个地,再八个八个地:
最后算出来的数字就是 1 的数量。这样做是 的。
一些现代的 CPU 内置了 popcnt 的指令。在 GCC 可以直接使用函数 __builtin_popcount
。但是这样会使得代码的可移植性变得稍微差一点。
归并排序中合并两个已经排好序的序列:
其中分支 1、2、4 都是可预测的,因为 CPU 可以假定条件永远成立,这样在大多数情况下都是预测正确的,如果预测错误,那么就结束循环,只会错误一次,至少预测永远成立不劣于预测永远不成立。而分支 3 无论预测成立还是不成立,似乎没有个轻重,所以是不可预测的。
通过消除不可预测的分支,我们可以提升性能,我们将代码变为:
c12345long cmp = (*A <= *B);
long min = *B ^ ((*B ^ *A) & (-cmp));
*C++ = min;
A += cmp; na -= cmp;
B += !cmp; nb -= !cmp;
不过实际上这么搞可能未必真的能提升性能,因为编译器可以选用条件传送指令。
大意就是在 的棋盘上放棋子,要求一个棋子所在位置的同一行、同一列、同一对角线上不能有其他棋子。朴素的做法就是 dfs 暴搜,枚举在一行的哪个位置放棋子是合法的,然后再 dfs 下一行,直到 行全部搜完。此时一个问题就是怎么比较好地 check 某个位置是否合法。
我们可以定义 down
变量的第 i
位表示第 i
列是否存在棋子。
不用记录某一行是否存在棋子,因为我们一行只放一个。
对角线有两个,一个是横纵坐标之和为定值,一个是横纵坐标之差为定值,可以根据这个来安排二进制位。