\(L=18\) とし，すべての数は（2進で） \(L\) 桁だとします． なお，ある数の \(k\) 桁目，といったときには，下から\(0\)-based index で \(k\) 番目の桁を指すことにします．

\(A_i \oplus A_j\) と \(B_i \oplus B_j\) が（上から見ていって）最初に異なる bit を考えます． これは，\(A_i \oplus A_j \oplus B_i \oplus B_j\) の最上位 bit です．

\(C_i = A_i \oplus B_i\) と 定義しておきます． \(C_i\) の \(W\)(\(=L-1\)) 桁目が \(0\) である \(i\) の集合を \(S\)，\(1\) であるような \(i\) の集合を \(T\) と置きます． \(i,j \in S\) もしくは \(i,j \in T\) を満たすペア \((i,j)\) の寄与は，\(W:=W-1\) とした上で，\(S,T\) それぞれで再帰的に計算することにします．

\(i \in S,j \in T\) なる \(i,j\) のペアの寄与を考えます． \(i \in S\) の中でさらに，\(A_i\) の \(W\) 桁目が \(0,1\) のものを集めてそれぞれ \(S_0,S_1\) と呼ぶことにします． 同様に，\(T_0,T_1\) を定義します． この時，各 \(0 \leq x,y \leq 1\) について，どの \(i \in S_x,j \in T_y\) についても，\(A_i \oplus A_j\) と \(B_i \oplus B_j\) のどちらが小さいかが一意に定まります．

よって，各 \(V=S_0,S_1,T_0,T_1\) について，以下の値を計算しておけばおいです．

• 各 \(0 \leq j < L\) について，\(A_i,B_i\) の \(j\) bit 目の分布．

計算量は全体で \(O((N+2^L) L^2)\) になります． （\(C_i=C_j\) なる \(i,j\) の寄与について説明していませんが，これは簡単なので省略します．）