Counting Bits
0以上の整数 n が与えられたとき、n+1 個の要素を持つ配列を返します。各 i について、i 番目の要素は、0から n までのすべての i の二進表記に含まれる1の数です。
関数
- ninteger
- 数える最後の数、0 以上
- 戻り値integer-array
- n+1個のカウントからなる配列で、i番目の要素はiに含まれる1ビットの数
制約
0 ≤ n ≤ 2 × 104
例
- 入力
- n = 2
- 出力
- [0, 1, 1]
- 説明
- 2進数では、0は
0、1は1、2は10です。1がない状態、次に1つ、そして1つです。
- 入力
- n = 5
- 出力
- [0, 1, 1, 2, 1, 2]
- 説明
- 3は
11で、5は101なので、それぞれ1が2つあります。4は100で、1が1つあります。最初の例の0、1、2と合わせると、個数は0、1、1、2、1、2です。
発展問題
ビットを数える組み込み関数を使わず、各数値を一から数え直すこともなく、O(n)時間で配列全体を埋められますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
0から8を2進数で書き、最後の桁を削除して得られる数と比較しましょう。6は
110で、3は11です。それぞれの1の個数はどのように比較できますか？1 ビット右にシフトする
i >> 1と、iの最後の2進数の桁が削除されます。iの個数は、i >> 1の個数に最後の桁であるi & 1を加えたものです。0から順に配列を埋めていきます。
iに到達したとき、i >> 1の要素はそれより小さいため、すでに埋まっています。したがって、各要素につき参照1回と加算1回で済みます。
解説
すべての数を最初から数えると、同じ作業を繰り返すことになります。13 は 1101 で、6 のビット列 (110) の末尾に 1 桁追加したものです。答えを小さい順に埋めていけば、各項目でより小さい値を再利用し、加算を 1 回行うだけで済みます。
各数値のビット数を数える
考え方
各数の1ビットを直接数えます。カウンターに x & 1 を加え、x を右に1ビットシフトし、0になったら停止します。13（1101）の場合、ビットは1、0、1、1となるため、個数は3です。
n 以下の数は約 log2 n 桁の2進数で表されるため、実行時間は O(n log n) です。n = 2 × 10^4 の場合、約20,000 × 15 = 300,000ステップです。
アルゴリズム
- 空の結果リストを開始します。
- 0から
nまでの各iについて、countを0に設定し、xをiに設定します。 xが0より大きい間、x & 1をcountに加え、xを右に1ビットシフトします。countを結果に追加します。- 結果を返します。
def countBits(n):
bits = []
for i in range(n + 1):
count = 0
x = i
while x > 0:
count += x & 1 # the lowest bit
x >>= 1 # shift it out
bits.append(count)
return bits数値の半分を基にする
考え方
iを右に1ビットシフトすると最後の2進数の桁が削除され、i & 1はその桁です。つまり、iの1の個数は、i >> 1の1の個数に最後の桁を加えたものです: bits[i] = bits[i >> 1] + (i & 1)。
1以上のすべてのiについて、i >> 1はiより小さいため、bits[0] = 0から始めて配列を左から右へ埋めていけば、読み取る値は常に準備できています。n = 5の場合: bits[3] = bits[1] + 1 = 2、bits[4] = bits[2] + 0 = 1、bits[5] = bits[2] + 1 = 2。
各要素の計算はシフト1回、AND 1回、加算1回です。時間計算量はO(n)で、出力以外のメモリは必要ありません。
アルゴリズム
n+1個のゼロを含む配列bitsを作成します。bits[0]は 0 のままです。iを 1 からnまで変化させ、bits[i]をbits[i >> 1] + (i & 1)に設定します。bitsを返します。
def countBits(n):
bits = [0] * (n + 1)
for i in range(1, n + 1):
# i >> 1 is i without its last bit, and i & 1 is that last bit
bits[i] = bits[i >> 1] + (i & 1)
return bits
落とし穴と境界ケース
n+1個ではなくn個の要素を返してしまう。n= 0 の場合、答えは[0]です。- 演算子の優先順位。Python、C、Java、JavaScript では、
+は&より優先順位が高いため、bits[i >> 1] + i & 1は(bits[i >> 1] + i) & 1を意味します。(i & 1)の括弧はそのままにしてください。 bits[i >> 1]ではなくbits[i-1]を参照してしまう。隣り合う数に単純な規則はありません。7 は 1 が3つの111で、8 は 1つの1000です。- Lua と R では配列のインデックスは 1 から始まるため、
iのカウントはインデックスi+1にあり、i >> 1の参照先はfloor(i/2) + 1になります。Lua 5.1 にはシフト演算子がないため、math.floor(i / 2)で半分にします。
よくある質問3
Counting Bits の時間計算量はどのくらいですか？
最適な解法は O(n) 時間で実行されます。n+1 個の各エントリは、1 回の加算で先行するエントリから求められます。各数値のビットを個別に数えると O(n log n) かかります。どちらも、出力配列以外に O(1) のメモリを使用します。
Counting Bits に対する、別の O(n) の漸化式はありますか？
はい。i & (i-1)はiの最下位の1ビットをクリアするため、1以上のすべてのiについてbits[i] = bits[i & (i-1)] + 1となります。12（1100）の場合、12 & 11は8（1000）で、1が1つあるため、12には1が2つあります。
組み込みのpopcount関数を使えますか？
Java の Integer.bitCount や C および C++ の __builtin_popcount のように、数値ごとに呼び出せば正しい答えが得られます。面接官が通常、これらを使わない方法を求めるのは、すでに計算した答えを再利用することがこの問題のポイントだからです。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def countBits(n):
# ここにコードを書いてくださいテスト #1
テスト #2
引数
n = 2
期待される出力
[0, 1, 1]