元の問題では \(x\) は正の整数となっていますが、0を含むことにしても答えは変わりません。「\(0\) 以上 \(N\) 以下の整数のうち、popcount が \(K\) であるものの和」を \(f(N,K)\) とおきます。

\(2^m\) を \(N\) 以下の最大の \(2\) ベキとして、下図のように3つの領域に分けて寄与を考えます。（左上の領域は必ず全て 0 なので考慮する必要はありません）

• 右上の領域の寄与は \(f(2^m-1,K)\) です。各bit に注目したとき、「\(0\) 以上 \(2^m-1\) 以下の整数で、popcountがKであり、指定されたbitが1であるもの」は \(\binom{m-1}{k-1}\) 個あります（指定された桁以外の \(m-1\) 箇所のうち \(K-1\) 個が 1 なので）。よって \(f(2^m-1,K)=(2^m-1)\binom{m-1}{k-1}\) となります。
• 左下の領域の寄与は \(2^m\times(0以上N-2^m以下の整数で、\text{popcount} がK-1であるものの個数)\) となります。
• 右下の領域の寄与は \(f(N-2^m,K-1)\) です。再帰的に計算します。

「\(0\) 以上 \(N-2^m\) 以下の整数で、popcount が\(K-1\) であるものの個数」も同様の再帰で求めることができます。

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

実装(Python)