記事の内容
この記事で紹介したいのは、
n までの整数の中で、2進数で表したときに j ビット目が1である数の個数を効率的に数える
という考え方を紹介します。
なぜこの考え方に注目したのか
AtCoderのABCにて出題されたこの問題を解くために必要な考え方だからです。
色々と勉強になる考え方なので、記録のために記事化しておきたいです。
整数問題やビットの考え方のいい練習になるはずです。
問題の具体化
目的は、n までの整数の中で、2進数で表したときに j ビット目が1である数の個数を数えることです。
n = 13 の場合の整数（0から13まで）を2進数で表すと次のようになります。
j＝２、つまり、２ビット目に注目します。
0: 0000
1: 0001
2: 0010
3: 0011
4: 0100
5: 0101
6: 0110
7: 0111
8: 1000
9: 1001
10: 1010
11: 1011
12: 1100
13: 1101
このとき、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 になるビットの個数を計算しています。