記事の内容

この記事で紹介したいのは、

n までの整数の中で、2進数で表したときに j ビット目が1である数の個数を効率的に数える

という考え方を紹介します。

なぜこの考え方に注目したのか

AtCoderのABCにて出題されたこの問題を解くために必要な考え方だからです。

色々と勉強になる考え方なので、記録のために記事化しておきたいです。
整数問題やビットの考え方のいい練習になるはずです。

問題の具体化

目的は、n までの整数の中で、2進数で表したときに j ビット目が1である数の個数を数えることです。
n = 13 の場合の整数（0から13まで）を2進数で表すと次のようになります。
j＝２、つまり、２ビット目に注目します。

このとき、2ビット目（j = 2）が1であるのは 4, 5, 6, 7, 12, 13 で、合計6つあります。
よって、求める数は６です。

答えを求めるコード

答えを求めるコードはこちらです。（くどいくらいコメントを入れています。）

# 関数 f(j, n): jビット目のカウントを計算する
def f(j, n):
    p2 = (1 << j)  # 2^j を計算
    k = n // (2 * p2)  # n を 2 * 2^j で割った商を計算
    res = k * p2  # 商に 2^j を掛けた結果を res に保存
    l = n % (2 * p2)  # n を 2 * 2^j で割った余りを計算
    if l >= p2:  # もし余りが 2^j 以上であれば
        res += (l - p2 + 1)  # res に (余り - 2^j + 1) を足す
    return res

なぜこのコードで計算できるのか

私は、最初にこのコードを見たときに、なぜこの方法で答えが得られるのかわかりませんでした。そのため、このコードで答えが求められる理由を具体的に解説します。

関数 f(j, n) のアルゴリズムが動作する理由は、2進数におけるビットの規則性を利用して、j ビット目が立っている（つまり 1 である）数を効率的に数えるためです。これを理解するために、ビットのパターンがどのように繰り返されるかを考えます。

2進数でのビットパターンの周期性

2進数では、各ビットは特定の周期で 0 と 1 を繰り返します。たとえば、ビットの位置が固定されている場合、そのビットが 1 になる回数には周期的なパターンがあります。

例えば、j = 2 の場合（2ビット目）、そのビットが 1 になるのは次のような周期で発生します。

ビットのパターン: 00 01 10 11 (4つの数ごとに周期)
4つの数（00, 01, 10, 11）のうち、2ビット目が 1 であるのは、10 と 11 のときです。

f(j, n) の具体的な流れ

k = n // (2 * p2)
この部分は、n を 2 * p2 で割り、その整数部分 k を得ることで、j ビット目が完全に周期を満たす回数を求めています。
例えば、p2 = 4 の場合、この計算は「j ビット目が 1 である完全な周期がいくつ含まれるか」を計算しています。周期ごとに p2 個のビットが 1 になるため、k * p2 がその範囲での 1 の個数となります。
l = n % (2 * p2)
次に、n が完全な周期に収まらない余り（残りの部分）を計算します。この余り部分が、次の部分での計算に使われます。
if l >= p2
ここで、余り l が p2 以上であれば、その残りの範囲でも j ビット目が 1 になる範囲があるため、その数だけ追加します。具体的には、余り l が p2 以上であれば、l - p2 + 1 の個数が 1 であると計算されます。

まとめ: なぜこの方法で求められるのか

ビットの周期性の利用: 2進数におけるビットの値が 0 と 1 を繰り返す周期性を利用しています。j ビット目が 1 になる周期を 2^j で表し、そのビットが 1 になる数の範囲を効率的に計算しています。
完全な周期のカウント: n を 2 * p2 で割ることで、j ビット目が 1 である完全な周期が何回含まれているかを数え、その中で 1 が出現する回数を計算しています。
部分的な周期の処理: 余りの部分を別途処理することで、n が完全な周期に含まれない場合でも、正確に 1 になるビットの個数を計算しています。

関連記事