Caiwen的博客

软件性能工程-位运算

2025-09-13 09:07

1. 位运算

一些位运算技巧

1.1 补码取反的关系

x + ~x = -1(因为自身加上对自身取反的话,那么二进制所有位都变成 1 了,按补码规则表示为 -1)

于是我们有 -x = ~x + 1

1.2 设置位

设置第 k 位:y = x | (1 << k)

清除第 k 位:y = x & ~(1 << k)

切换第 k 位:y = x ^ (1 << k)

1.3 交换数字

c
1
2
3
x = x ^ y; // 此时 x 相当于把原来的两个数字合在了一起 y = x ^ y; // 合在一起之后异或 y 就相当于把 y 消掉,取出 x x = x ^ y; // 同上

不过这个技巧未必性能更优。因为上面三个操作之间有严重的数据依赖,导致指令的并行性很差。对比传统的引入临时变量来交换:

c
1
2
3
temp = x; x = y; y = temp;

CPU 可以同时取出 xy 然后并行地执行前两个操作。朴素的做法指令的并行性更好。

1.4 取 min

r = min(x, y) = y ^ ((x ^ y) & -(x < y))

如果 x < y ,那么 -(x < y) 为 -1,二进制下全 1,使得最后结果为 (y ^ (x ^ y)) = x。而如果 x >= y 的话后面那堆东西就为 0。

相比于朴素做法,直接通过判断取 min 的话,分支预测错误的代价比较大。不过也不好说,因为编译器应该会使用条件传送吧()

1.5 加法取模

c
1
2
3
z = x + y; r = z - (n & -(z >= n)); // 第二行等价于 r = (z < n) ? z : z - n; 这里使用了类似取 min 的技巧

1.6 向上取整到 2 的幂次

其大概思想就是将 n - 1 中的所有二进制位都向后覆盖,最后低位都是 1,再加一个 1 就变为 2 的幂次了:

其中 -1 是为了处理 n 已经是 2 的幂次的情况。

1.7 lowbit

r = x & (-x);

树状数组学过,这里再复习一下:

这里的 -x~x + 1,其中对 x 取反之后,原来的 lowbit 就变为 0,而 lowbit 之前的位全变为了 1,此时我们直接再 + 1,lowbit 之前的位全部进 1,使得 lowbit 又变为 1 了,而 lowbit 之后的位仍然不变,这使得再按位与的时候后面都是 0。

1.8 对 2 的幂次取 log

这里的取 log 的底数是 2,也就是我们想知道一个 2 的幂次的指数。

原理是 deBruijn 序列。这种序列满足,序列中任意长度为 kk 的区间内的位表示的数字都是不同的,比如:

其中的 00011101 就是一个 deBruijn 序列。我们可以得到一个 convert 数组,记录一个二进制下的三位数在上面的第几行出现。

然后我们考虑,如果我们把这个 deBruijn 序列左移 xx 位,然后取出高 k=3k=3 位,就相当于拿到一个特征值,然后此时这个 xx 就对应于上图中左边的数字。如果我们不知道 xx,仅凭特征值和 convert 数组仍然可以得知这个 xx

回到最开始的问题,对于 2 的幂次 nn,我们直接让 deBruijn 乘上这个 nn,就相当于进行了左移。

后面我查了一下如何构造 deBruijn 序列,可以使用求欧拉回路的算法。比如我们有如下的图:

一种欧拉回路是 01011100 (从点 00 出发)。再验证一下,确实是 deBruijn 序列。

我们现在想要通过一个长度为 kk 的区间,在 deBruijn 序列上滑动,得到所有的三位二进制数。当区间向右滑动时,低两位就变成了高两位,得到的新的数字的低两位数字发生了变化。我们将低两位看成是一个状态,对应于图上的点。在当前状态下再追加一个二进制位看成是状态的转移,对应于图上的有向边。然后在图上,点和连出去的边组合在一起就是一个三位的二进制数。如果存在一个回路能把所有的边覆盖,我们也就相当于覆盖了所有的数字,而这就是欧拉回路。

1.9 popcnt

朴素的做法就是直接逐位枚举统计。

我们还可以多个位多个位地统计:

理论上我们一次统计的位数越多,循环次数越少,速度越快。但是还需要考虑到缓存的影响,count 数组越大,其缓存的利用率越小,可能反而增加时间。

还有一种分治的算法:

大概思想就是,两个两个地计算 1 的数量,然后再四个四个地,再八个八个地:

最后算出来的数字就是 1 的数量。这样做是 O(logN)O(\log N) 的。

一些现代的 CPU 内置了 popcnt 的指令。在 GCC 可以直接使用函数 __builtin_popcount 。但是这样会使得代码的可移植性变得稍微差一点。

2. 例子

2.1 例:消除不可预测的分支

归并排序中合并两个已经排好序的序列:

其中分支 1、2、4 都是可预测的,因为 CPU 可以假定条件永远成立,这样在大多数情况下都是预测正确的,如果预测错误,那么就结束循环,只会错误一次,至少预测永远成立不劣于预测永远不成立。而分支 3 无论预测成立还是不成立,似乎没有个轻重,所以是不可预测的。

通过消除不可预测的分支,我们可以提升性能,我们将代码变为:

c
1
2
3
4
5
long cmp = (*A <= *B); long min = *B ^ ((*B ^ *A) & (-cmp)); *C++ = min; A += cmp; na -= cmp; B += !cmp; nb -= !cmp;

不过实际上这么搞可能未必真的能提升性能,因为编译器可以选用条件传送指令。

2.2 例:八皇后问题

大意就是在 8×88\times 8 的棋盘上放棋子,要求一个棋子所在位置的同一行、同一列、同一对角线上不能有其他棋子。朴素的做法就是 dfs 暴搜,枚举在一行的哪个位置放棋子是合法的,然后再 dfs 下一行,直到 88 行全部搜完。此时一个问题就是怎么比较好地 check 某个位置是否合法。

我们可以定义 down 变量的第 i 位表示第 i 列是否存在棋子。

不用记录某一行是否存在棋子,因为我们一行只放一个。

对角线有两个,一个是横纵坐标之和为定值,一个是横纵坐标之差为定值,可以根据这个来安排二进制位。