求める答えを \(f(N,M)\) とおきます。\(f(0,M)=0\) と \(f(1,M)=M\&1\) は明らかです。以下 \(N\geq 2\) とします。

\(N\) の最上位 bit の寄与を考えます。\(N\) の最上位 bit が \(k\) bit 目であるとします。（例えば\(N=1100_{(2)}\) なら \(k=3\)）

下図のように3つの領域に分けて寄与を考えます。（左上の領域は必ず全て \(0\) なので考慮する必要はありません）

• 右上の領域の寄与は \(f(2^k-1,M)\) であり、どの桁にもちょうど \(2^{k-1}\) 個の \(1\) があることから、この値は \(\mathrm{popcount}(M\&(2^k-1))\times 2^{k-1}\) に等しくなります。
• 左下の領域には \(N-(2^k-1)\) 個の \(1\) があります。よってこの領域の寄与は \(M\) の \(k\) bit 目が \(1\) のとき \(N-(2^k-1)\)、\(0\) のとき \(0\) です。
• 右下の領域の寄与は \(f(N-2^k,M)\) です。再帰的に計算します。

再帰するごとに第一引数の2進での桁が1つ以上減るので、全体で \(O(\log N)\) で計算できます。