Counting Bits
0以上の整数 n が与えられます。0から n までの各数 i について、i を2進数で表したときに1がいくつ現れるか数えてください。各要素 i が数 i の個数を表す、n+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が0個、次に1個、そして1個です。
- 入力
- n = 5
- 出力
- [0, 1, 1, 2, 1, 2]
- 説明
- 3 は
11で、5 は101なので、それぞれ 1 が 2 つあります。一方、4 は100で、1 は 1 つだけです。最初の例の 0、1、2 と合わせると、0 から 5 までの 1 の個数は 0、1、1、2、1、2 です。
提出時に隠しテスト+15件
発展問題
ビットを数える組み込み関数を使わず、また各数値を最初から数え直すことなく、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回が必要です。
解説
各数の1の個数を個別に数える方法でも動作しますが、同じ作業を繰り返します。13は1101、6は110です。13のビットは、6のビットの末尾にもう1桁加えたものです。答えを小さい順に埋めていけば、iに必要な個数はすでに配列にあり、各要素は1回の加算で求められます。
各数値のビット数を数える
考え方
0からnまでの各数について、1のビットを直接数えます。xの最下位ビットはx & 1です。それをカウンターに加え、x >> 1でxを右にシフトして、次のビットを最下位にします。xが0になったら終了します。
13は1101なので、右からビットを取り出すと1、0、1、1となり、カウントは3です。各数の処理には2進数の桁数に応じたステップ数がかかり、n以下の数の桁数はおよそlog2 nです。
そのため、全体の処理時間はO(n log n)です。n = 2 × 10^4の場合、およそ20,000 × 15 = 300,000ステップとなり、時間内に実行できます。それでも作業の一部が無駄になります。13を数えるとき、6ですでに行った各ステップを繰り返すからです。出力配列を除く空間計算量はO(1)です。
アルゴリズム
- 空の結果リストを作成します。
- 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の1ビットの数に、最後の桁が1の場合はさらに1を加えたものと同じです。最後の桁はi & 1なので、規則はbits[i] = bits[i >> 1] + (i & 1)となります。
1以上のすべてのiについて、i >> 1はiより小さくなります。bits[0] = 0から始めて配列を左から右へ埋めていけば、参照する要素は必ずすでに埋まっています。これは動的計画法です。それぞれの答えを、より小さな値の答えから作ります。
n = 5の場合：bits[1] = bits[0] + 1 = 1、bits[2] = bits[1] + 0 = 1、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
落とし穴と境界ケース
規則は1行で表せるため、バグはその周辺に潜んでいます。
- 配列の要素数は
nではなくn+1です。n= 0 の場合、答えは[0]です。0という数のための要素が1つあります。 - 演算子の優先順位。Python、C、Java、JavaScriptでは、
+は&より優先順位が高いため、bits[i >> 1] + i & 1は(bits[i >> 1] + i) & 1と解釈されます。(i & 1)の括弧は残してください。 bits[i >> 1]ではなくbits[i-1]を参照してしまう。隣り合う数には単純な規則がありません。7は111で1が3つ、8は1000で1つです。- LuaとRでは配列のインデックスが1から始まるため、
iの個数はインデックスi+1にあり、i >> 1の参照先はインデックスfloor(i/2) + 1です。実行環境のLuaにはシフト演算子がないため、math.floor(i / 2)で半分にしてください。 - 各数を二進数の文字列に変換して
1の文字を数えれば正しい答えが得られますが、数ごとに新しい文字列を作ることになります。
よくある質問4
Counting Bits の時間計算量はどれくらいですか？
最適な解法は O(n) 時間で実行されます。n+1 個の各要素は、1つ前の要素に1を加えて求められます。各数値のビットを1つずつ数えると O(n log n) かかります。これは、n 以下の数値が約 log2 n 桁の2進数で表されるためです。どちらも、出力配列以外に必要なメモリは O(1) です。
なぜ <code>bits[i] = bits[i >> 1] + (i & 1)</code> は機能するのでしょうか？
i >> 1 は最後の2進数の桁を取り除いた i であり、i & 1 は取り除かれたその桁です。i に含まれる1の数は、より短い数に含まれる1の数に最後の桁を加えたものです。11は 1011 で、より短い数は5（101、1が2つ）で、最後の桁は1なので、11には1が3つあります。
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問解くとパターンが身につきます。
Python
def countBits(n):
# ここにコードを書いてくださいケース1
ケース2
入力
n = 2
期待値
[0, 1, 1]