成对变换
对于非负整数\(n\):
当\(n\)为偶数时，\(n xor 1\)等于\(n+1\)
当\(n\)为奇数时，\(n xor 1\)等于\(n - 1\)
“0 和 1”， “2 和 3”， “4 和5”......关于\(xor 1\)运算构成“成对变换”
这一性质常用于图论邻接表中边集的存储。在具有无向边（双向边）的图中把一对正反方向的边分别存储在邻接表数组的第\(n\）和\(n+1\)位置（\(n\)是偶数）
通过\(xor 1\)运算可以得到当前边和反向边的存储位置。
\(lowbit\)
\(lowbit(n)\)定义为非负整数\(n\)在二进制表示下“最低位的1及其后边所有的0”构成的数值。
\(lowbit(n) = n & (~n + 1) = n & (-n)\)
因为假设\(n\)的第\(k\)位是\(1\)， 第\(0~k-1\)位都是\(0\)
\(~n\)的第\(k\)为是\(0\)， 第\(0~k-1\)都是\(1\)
那么\(~n + 1\)的第\(k\)是\(1\)， 第\(0~k-1\)都是\(0\)
其实根据补码的一种求法也可以知道，\(~n +1\)的高位到第\(k+1\)位都和\(n\)相反，\(0~k\)位不变。
进行\(&\)运算后得到的就是\(lowbit(n)\)
\(lowbit\）加Hash可以找出整数二进制表示下所有是1的位，复杂度与1的个数同级。只需要每次做\(n = n - lowbit(n)\)的操作
原文：https://www.cnblogs.com/wyboooo/p/9951397.html