yukicoder No.737 PopCount - phyllo’s algorithm note

問題

Nが与えられる。
$\Sigma_{i = 1}^N {i * popcount(i)}$ を求めよ。
(popcount(i)は、iを2進数表記したときの立っているビットの数)

制約

1 <= N <= 10^18

解法

法則性がないか見るために、各数字のビットを書き出してみる。
f:id:phyllo_algo:20180929013409p:plain

1bit目が1になるものは、{1},{3},{5},{7},{9},...
2bit目が1になるものは、{2,3},{6,7},{10,11},...
3bit目が1になるものは、{4,5,6,7},{12,13,14,15},...

各bit目ごと(上の表の縦方向)に見ると、「塊が等間隔で現れている」という法則性が確認できる。
そこで、「x bit目について、N以下でbitが立っている数字の和」を求める方法を考えれば、それぞれのxで求めたものを足せば答えが得られる。

ということで、「x bit目について、N以下でbitが立っている数字の和」を考える。
最初の塊は、最初の数字が2^{x-1}で、x個続いている。
また、塊は間隔が2^xごとになっており、塊の数は、等差数列より「(N-2^{x-1})/2^x + 1」個ある。
したがって、これらは「等差数列の和の公式 Sn = n / 2 * (2*a + (n-1) * d)」を使えばO(1)で求められる。
また、Nが固まりの途中までの場合は、N+1から塊の最後の数字までの分の和を引いてあげればよい。