いちばん下の 1 を消していき、2 進の 1 の数を数える

ビット操作問題 152

0 以上の整数を 2 進で書いたときの 1 の数を返します。n & (n - 1) でいちばん下の 1 のビットを 1 つずつ消せば、1 の数の回数だけ回して数えられる練習です。

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

問題

部屋の照明の状態を、32 個のスイッチの 1 と 0 として 1 つの整数 n に詰めて持っています。2 進で書いた n に 1 がいくつあるか、つまり点いている照明の数を返す関数を書いてください。

  • n は 0 以上 4294967295 (2 の 32 乗から 1 を引いた数) 以下です
  • 言語に備わった 1 の数を数える関数 (bin(n).count、bits.OnesCount など) は使わずに書いてください

入力と出力の例

例 1

13 は 2 進で 1101 です。

n = 13
3

例 2

1024 は 2 の 10 乗で、1 は 1 つだけです。

n = 1024
1

例 3

255 は 2 進で 1 が 8 個並びます。

n = 255
8

面接での聞かれ方

面接では、ビット演算の基本を確かめる問題として出されます。

  • 「整数の 2 進表現の 1 の数を返してください」
  • 1 ビットずつ見る書き方を見せると、「1 の数だけ回して数えられますか？」と続きます
  • 「この関数を何百万回も呼ぶならどうしますか？」と聞かれることもあります

n & (n - 1) の意味を、ビットを書いて説明できるかが見られています。

ヒント

まだ開いていません

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

  2. ヒント 2

  3. ヒント 3答えに近い

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

関わる学び

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

main.py
def count_one_bits(n: int) -> int:
    """
    Goal: 何を返すか

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

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

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


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

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