No.130

$x$ の最上位ビットを立てたときの $x \oplus a_i$ の最大値は, $a_i$ の最上位ビットが立っていないものだけ集めて, 残りのビットについて計算した結果となる.

$x$ の最上位ビットを立てなかったときの $x \oplus a_i$ の最大値は, $a_i$ の最上位ビットが立っていないものだけ集めて, 残りのビットについて計算した結果となる.

両者を比較して小さい方を採用するようにする.

これを再帰的に計算すればいい. $a_i$ が絞られていくので, $O(\log N)$ で計算できる.