Delta Swapの簡単解説

はじめに: 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をしている、と理解できます。おわり。

さいごに

図が汚い。