ビットごとに計算する. なお, ビットは0-indexedとする.

第 \(k\) ビットを計算することを考える. \(T = 2^k\) とする.

この計算には \(k+1\) ビット以降は必要ないので, \(\{ a_i \}, \{ b_j \}\) はあらかじめ \(2T\) で剰余を取っておく.

そうすると \(a_i \lt 2T, b_j \lt 2T\) なので, \(a_i + b_j \lt 4T\) となる.

\(a_i + b_j\) の第 \(k\) ビットが立っている状態というのは, \(a_i + b_j\) が \([T, 2T), [3T, 4T)\) の区間にあることである. \(a_i\) を固定すれば \(b_j\) が \([T-a_i, 2T-a_i), [3T-a_i, 4T-a_i)\) の区間にあることになるので, \(b_j\) をソートして二分探索でこのような \(b_j\) の個数を計算できる.

これをすべての \(a_i\) で計算して合計し, 偶奇を見れば第 \(k\) ビットの値が分かる.