#はじめに: Delta Swapとは？
あるビット列において、そのビット列の部分ビット列（連続でなくてもよい）のうち、同じ形のもので、被りがないもの2組を入れ替える操作のことです。
これを次のようなコードで実現できます。
delta_swap.cpp
typedef unsigned long long ull;
ull delta_swap(ull x, ull mask, int delta) {
ull t = (x >> delta) ^ x & mask;
return t ^ (t << delta) ^ x;
}
x は対象のビット列、mask は入れ替えたい2組の部分ビット列のうち、下位に位置する方が占めるビットをすべて1で埋めたものです。
mask と mask << delta が示す2組の部分ビット列を入れ替えます。
この記事では、このコードの一つの理解の仕方を書きます。
前提知識（？）
上のコードを理解する上では、一見当たり前に見える次の恒等式が重要になります。
delta_swap.cpp
A ^ B ^ B = A
順番を入れ替えても同じ
delta_swap.cpp
(B ^ A) ^ B = A
これを利用すれば、一時変数を使わない2つの変数のswapが書けます。
delta_swap.cpp
// A, Bはリテラルの意味で、C, Dは変数の意味で使います
// C, Dの中身を入れ替えます
// 最初CにはA, DにはBが入っているとします。
C ^= D; // CにA^Bが入る
D ^= C; // DはB^(A^B), すなわちAが入る
C ^= D; // (A^B)^A, すなわちB
本題: Delta Swap 解説
まず
delta_swap.cpp
ull t = (x >> delta) ^ x & mask;
は、2つの入れ替えたいビット列のxorを作っているとみなせます。
よって、
delta_swap.cpp
return t ^ (t << delta) ^ x;
は、もとのビット列 x にこのxorしたものをxorすることによって（日本語がカオス）、ビット列のswapをしている、と理解できます。おわり。
##さいごに
図が汚い。