\(p(n) = \rm{popcount}(n)\) として, \(n\) を \(p(n)\) で割ったあまりを \(m(n)\) とする.

このとき, \(f(n) = f(m(n)) + 1\) となる. \(m(X) \lt N\) となるので, \(f(n) \ (1 \leq n \lt N)\) はあらかじめ計算しておく.

さて, \(m(X_i)\) を考える. \(p(X_i)\) は \(p_- = p(X)-1\) か \(p_+ = p(X)+1\) のどちらかである. そこで, \(2^k\) を \(p_-\) で割ったあまりと \(p_+\) で割ったあまりを計算する. これは剰余の性質から \(2^{k-1}\) の計算結果からすぐに求められる. そして \(X\) を \(p_-\) で割ったあまりと \(p_+\) で割ったあまりも計算する.

このとき, \(m(X_i)\) は, \(X\) の \(i\) ビット目が \(0\) のときは \(m(X+2^i)\) となり, \(1\) のときは \(m(X-2^i)\) となる. 剰余の性質と上記の計算結果を用いることでこれはすぐに計算でき, \(f(m(X_i))\) もあらかじめ計算してあるので \(f(X_i)\) は \(O(1)\) で計算できる.