【位运算】二进制状态压缩、成对变换、lowbit运算-Toy模板网

这篇具有很好参考价值的文章主要介绍了【位运算】二进制状态压缩、成对变换、lowbit运算。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1、二进制状态压缩

二进制状态压缩，是指将一个长度为 $m$ 的 bool 数组用一个 $m$ 位二进制整数表示并存储的方法。

利用下列位运算操作可以实现原 bool 数组中对应下标元素的存取。

操作	运算
取出整数 $n$ 在二进制表示下的第 $k$ 位	(n >> k) & 1
取出整数 $n$ 在二进制表示下的第 $0$ ~ $k - 1$ 位	n & ((1 << k) - 1)
把整数 $n$ 在二进制表示下的第 $k$ 位取反	n ^ (1 << k)
对整数 $n$ 在二进制表示下的第 $k$ 位赋值 1	n \| (1 << k)
对整数 $n$ 在二进制表示下的第 $k$ 位赋值 0	n & (~(1 << k))

这种方法运算简便，且节省了程序运行的时间和空间。当 $m$ 不太大时，可以直接使用一个整数类型存储。当 $m$ 较大时，可以使用若干个整数类型（int数组），也可以直接利用 C++ STL 提供的 bitset 实现。

2、成对变换

对于非负整数 $n$ ：

当 $n$ 为偶数时，n ^ 1 等于 $n + 1$
当 $n$ 为偶数时，n ^ 1 等于 $n - 1$

因此，“0 与 1” “2 与 3” “4 与 5” … 关于 ^ 1 运算构成 “成对变换”。

这一性质经常用于图论邻接表中边集的存储。在具有无向边（双向边）的图中把一对正反方向的边分别存储在邻接表数组的第 $n$ 与 $n + 1$ 位置（其中 $n$ 为偶数），就可以通过 ^ 1 的运算获得与当前边 $(x, y)$ 反向的边 $(y, x)$ 的存储位置。

3、lowbit运算

lowbit(n) 定义为非负整数 $n$ 在二进制表示下 “最低位的 1 及其后边所有的 0” 构成的数值。 如 $n = 10$ 的二进制表示为 $1010)_2$ ，则 $lowbit(n) = 2 = (10)_2$ 。

推导 $l o w bi t (n)$ 的公式。

设 $n > 0$ ， $n$ 的第 $k$ 位是 1，第 $0$ ~ $k - 1$ 位都是 0。

为了实现 lowbit 运算，先把 $n$ 取反，此时的第 $k$ 为变成 0，第 $0$ ~ $k - 1$ 位都是1。再令 $n = n + 1$ ，此时因为进位，第 $k$ 为变为1，第 0 ~ $k - 1$ 位都是0。

在上面取反加1操作后， $n$ 的第 $k + 1$ 位到最高位恰好与原来相反，所以 n & (~n+1) 仅有第 $k$ 位为1，其余位都是0。而在补码表示下，~n = -1 - n，因此

lowbit(n) = n & (~n + 1) = n & (-n)

lowbit 运算配合 Hash 可以找出整数二进制表示下所有是 1 的位，所花费的时间与 1 的个数同级。为达该目的，只需不断把 n 赋值为 n - lowbit(n)，直至 $n = 0$ 。

例如，n = 9 = (1001)₂，则 lowbit(9) = 1。把 n 赋值为 9 - lowbit(9) = 8 = (1000)₂，则 lowbit(8) = 8 = (1000)₂。此时 8 - lowbit(8) = 0，停止循环。在整个过程中减掉了 1 和 8 = (1000)₂ 两个数，它们恰好是 n 每一位上的 1 后面补 0 得到的数值。取 1 和 8 的对数 log₂1 和 log₂8，即可得知 $n$ 的第 0 位和第 3 位是 1。因为 C++ math.h 库的 log 函数是以 e 为底的实数运算，并且复杂度常数较大，所以需要预处理一个数组，通过 Hash 的方法代替 log 运算。

当 n 较小时，最简单的方法是直接建立一个数组 H，令 H[2^k] = k，程序如下：

const int MAX_N = 1 << 20;
int H[MAX_N + 1];
for (int i = 0; i <= 20; i++) H[1 << i] = i; //预处理
while (cin >> n) {
	while (n > 0) {
		cout << H[n & -n] << ' ';
		n -= n & -n;
	}
	cout << endl;
}

稍微复杂但效率更高的方法是建立一个长度为 37 的数组 H，令 H[2 ^k mod 37] = k。这里利用了一个小的数学技巧： $\forall k \in [0,35], 2^k$ mod 37 互不相等，且恰好取遍1 ~ 36。需要之后的程序为：

int H[37];
for (int i = 0; i < 36; i++) H[(1ll << i) % 37] = i;

while (cin >> n) {
	while (n > 0) {
		cout << H[n & -n] << ' ';
		n -= n & -n;
    }
    cout << endl;
}