Let \(L=18\) and consider every number to have \(L\) digits (in binary). Below, when we say the \(k\)-th bit of a number, it refers to the \(k\)-th bit (\(0\)-indexed) from the bottom.

Consider the first bit (from the top) where \(A_i \oplus A_j\) and \(B_i \oplus B_j\) differ. This is the topmost bit of \(A_i \oplus A_j \oplus B_i \oplus B_j\).

Let \(C_i = A_i \oplus B_i\). Let \(S\) be the set of \(i\) such that the \(W\)(\(=L-1\))-th bit of \(C_i\) is \(0\), and \(T\) be the set of \(i\) such that the \(W\)-th bit of \(C_i\) is \(1\). For the pairs \((i,j)\) such that \(i,j \in S\) or \(i,j \in T\), we will compute their contribution recursively in each of \(S\) and \(T\) after letting \(W:=W-1\).

Let us consider the contribution of pairs \((i,j)\) such that \(i \in S,j \in T\). For \(i \ in S\), we will further divide these indices into sets \(S_0\) and \(S_1\), which consist of \(i\) such that the \(W\)-th digit of \(A_i\) is \(0\) and \(1\), respectively. \(T_0\) and \(T_1\) are similarly defined. Then, for each pair \(0 \leq x,y \leq 1\), for any \(i \in S_x\) and any \(j \in T_y\), the smaller of \(A_i \oplus A_j\) and \(B_i \oplus B_j\) is uniquely determined.

Therefore, we can find the answer by computing the following for each \(V=S_0, S_1, T_0, T_1\):

• the distribution of the \(j\)-th bits of \(A_i\) and \(B_j\) for each \(0 \leq j < L\).

The total complexity will be \(O((N+2^L) L^2)\). (We omitted the contribution of pairs \((i, j)\) such that \(C_i=C_j\), because it is simple.)