分类
Level4

成对变换

通过计算可以发现,对于非负整数 n:

当 n 为偶数时,n ^ 1 等于 n + 1 ;
当 n 为奇数时,n ^ 1 等于 n − 1 ;
因此,“0 与 1” “2 与 3” “4 与 5” … 关于 n ^ 1 运算构成 “成对变换”。

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