\(\displaystyle \sum_{i=1}^N \sum_{j=1}^N f(A_i+A_j)\) を代わりに求めます（対角線を引いて \(2\) で割って対角線を足せばもとの問題の答えになります）。

以下では \(\bm{1}[\cdot]\) で指示関数を表します。

\(\begin{aligned} &\phantom{=} \sum_{i=1}^N \sum_{j=1}^N f(A_i+A_j) \\ &= \sum_{i=1}^N \sum_{j=1}^N \sum_{k \geq 0} \frac{A_i+A_j}{2^k} \cdot \bm{1}\left[A_i+A_j \ は \ 2^k \ で割り切れるが \ 2^{k+1} \ で割り切れない\right] \\ &= \sum_{i=1}^N \sum_{j=1}^N \sum_{k \geq 0} \frac{A_i+A_j}{2^k} \cdot \left(\bm{1}\left[A_i+A_j \equiv 0 \pmod{2^k} \right] - \bm{1}\left[A_i+A_j \equiv 0 \pmod{2^{k+1}} \right]\right) \\ &= \sum_{i=1}^N \sum_{k\geq 0} \frac{A_i}{2^k} \left(\underbrace{\sum_{j=1}^N \bm{1}\left[A_j \equiv -A_i \pmod{2^k} \right]}_{\coloneqq C_k[-A_i]} - \underbrace{\sum_{j=1}^N \bm{1}\left[A_j \equiv -A_i \pmod{2^{k+1}} \right]}_{\coloneqq C_{k+1}[-A_i]} \right) \\ &\phantom{=} \quad + \sum_{i=1}^N \sum_{k\geq 0} \frac{1}{2^k} \left(\underbrace{\sum_{j=1}^N A_j \cdot \bm{1}\left[A_j \equiv -A_i \pmod{2^k} \right]}_{\coloneqq S_k[-A_i]} - \underbrace{\sum_{j=1}^N A_j \cdot \bm{1}\left[A_j \equiv -A_i \pmod{2^{k+1}} \right]}_{\coloneqq S_{k+1}[-A_i]} \right) \end{aligned}\)