位运算遍历所有非0位

遍历非0位

比如一个int，表示当前点与其他点的链接情况。每一位表示对应位表示与对应的id有边，则如何快速遍历所有的边呢？

参考自：hihocoder

方法

rest表示当前节点还可以走到的未访问节点。由于&运算的性质，只有当unused和edge[ nowVertex ]对应二进制位同时为1时，rest对应的二进制位才会为1。其含义就是该节点尚未访问，且节点nowVertex可以到达该节点。

while (rest) {
    int tp = rest & (-rest);
    dfs(p[ tp ], unused - tp);
    rest -= tp;
}

该循环的作用是枚举每一个可以到达的点。

int tp = rest & (-rest);

这里利用了一个性质，即p & -p等于取出p的最右边的一个1。举个例子p=10110:

   +---+---+---+---+---+
p  | 1 | 0 | 1 | 1 | 0 | 
   +---+---+---+---+---+
-p | 0 | 1 | 0 | 1 | 0 | 
   +---+---+---+---+---+
&  | 0 | 0 | 0 | 1 | 0 | 
   +---+---+---+---+---+

我们不断的利用这个性质从rest里面取出可以使用的二进制位，进行dfs(p[ tp ], unused - tp);。同时再枚举完一个节点后，将其从rest中删除，即rest -= tp;。