半分の数の答えを使い回し、0 から n までの 1 のビットの数を並べる

ビット操作問題 153

0 から n までの各数について、2 進で書いたときの 1 の数を並べて返します。i を 1 ビット右へずらした数の答えはもう出ているので、それにいちばん下のビットを足すだけで次々に埋まる練習です。

海外で定番の問題リスト 4 本には入っていません

問題

整数 n を受け取ります。長さ n + 1 の並び out を作り、out[i] に「i を 2 進で書いたときの 1 の数」を入れて返す関数を書いてください。i は 0 から n までです。

1 つの数ごとにビットを全部数える書き方ではなく、全体を O(n) の時間で埋める書き方を目指してください
n は 0 以上 100000 以下です

入力と出力の例

例 1

0 から 6 は、2 進で 0、1、10、11、100、101、110 です。

n = 6

[0, 1, 1, 2, 1, 2, 2]

例 2

n が 0 なら、0 の分だけの並びです。

n = 0

[0]

例 3

8 は 1000 で 1 は 1 つ、9 は 1001 で 2 つです。

n = 9

[0, 1, 1, 2, 1, 2, 2, 3, 1, 2]

面接での聞かれ方

面接では、ビット演算と動的計画法をつなぐ問題として出されます。

「0 から n までの各数の 1 のビットの数を返してください」
数ごとに数える書き方を見せると、「全体を O(n) にできますか？」と続きます
「前の答えのどれを使えば、次の答えが出ますか？」と、手がかりをもらえることもあります

前に出した答えを使い回せる形に気づけるかが見られています。

ヒント

まだ開いていません

付箋は 3 枚。下の段ほど答えに近づきます

ヒント 2
ヒント 3答えに近い

アルゴリズムのチートシートの「配列と文字列」に、この型の要点を表とコードでまとめています。

配列と文字列の問題は、全部の組を調べると手間が大きくなる所を、窓や左右の添字で減らす形が多いです。

まず考える手順

段 1

まずは素直に、数ごとに 1 ビットずつ見て 1 を数えます。1 つの数が 17 ビットほどなので、全体で O(n log n) です。正しく動きますが、前に数えた結果を使っていません。

段 2

i を 1 ビット右へずらした数 i >> 1 は、i のいちばん下のビットを落とした数です。i >> 1 は i より小さいので、その 1 の数はもう out に入っています。i の 1 の数は、それに落としたビット i & 1 を足した値です。

段 3

out[0] を 0 にし、i を 1 から n まで順に out[i] = out[i >> 1] + (i & 1) で埋めます。1 つの数につき 1 回の計算で済みます。

解答

Python

def counting_bits(n):
    out = [0] * (n + 1)
    for i in range(1, n + 1):
        out[i] = out[i >> 1] + (i & 1)
    return out

JavaScript

function countingBits(n) {
  const out = new Array(n + 1).fill(0);
  for (let i = 1; i <= n; i++) {
    out[i] = out[i >> 1] + (i & 1);
  }
  return out;
}

Go

func countingBits(n int) []int {
	out := make([]int, n+1)
	for i := 1; i <= n; i++ {
		out[i] = out[i>>1] + i&1
	}
	return out
}

Go では & が + より先に計算されるので、括弧が無くても out[i>>1] + (i & 1) と同じです。Python と JavaScript は + が先なので、括弧が要ります。

計算量

時間は O(n) です。1 つの数につき 1 回の計算です
使う記憶は、答えの並びを除けば O(1) です
out[i] = out[i & (i - 1)] + 1 (いちばん下の 1 を消した数の答えに 1 を足す) と書いても、同じく O(n) です

よくある間違い

Python や JavaScript で括弧を落とす。 out[i >> 1] + i & 1 は (out[i >> 1] + i) & 1 と読まれ、0 か 1 しか入りません
長さを n にする。 0 から n までは n + 1 個です。例 2 で空の並びを返してしまいます
i を 0 から回して out[0 >> 1] を読む。 0 では自分自身を読むだけなので害はありませんが、0 は最初から 0 と決めておき、1 から回すと読みやすくなります

解答を動かした版 Python 3.14.7Node.js 24.22.1Go 1.24.2確認日 2026年11月8日

main.py

def counting_bits(n: int) -> list[int]:
    """
    Goal: 何を返すか

    idea1: まず思いつく案
    -> runtime: O(?)  space: O(?)

    idea2: もっと速い案
    -> runtime: O(?)  space: O(?)

    edge case: 空、1 つだけ、など
    """
    # ここに書きます
    pass


# 「実行」を押すと、この行の結果が出ます
print(counting_bits(6))

できているか「例で確かめる」を押すと、問題の例を全部この関数に渡して、通ったかをここに出します