Number of 1 Bits
0以上の整数 n が与えられます。n を2進数で表し、その桁のうち1であるものの個数を返してください。この個数は、セットビット数、ポピュレーションカウント、またはハミング重みとも呼ばれます。たとえば、6は2進数で 110 なので、1のビットが2つあります。
関数
- ninteger
- 符号付き32ビット整数に収まる非負の整数
- 戻り値integer
- nの2進表記に含まれる1の桁数
制約
0 ≤ n ≤ 231-1
例
- 入力
- n = 11
- 出力
- 3
- 説明
- 11 は2進数で
1011です。これは 8 + 2 + 1 です。4桁の2進数のうち3桁が1なので、答えは3です。
- 入力
- n = 128
- 出力
- 1
- 説明
- 128は2^7で、
10000000と書きます。1の後に0が続くため、答えは1です。
- 入力
- n = 2147483645
- 出力
- 30
- 説明
- 2^31-1 = 2147483647 は、1 が31個連続した数です。2147483645 はその数から 2 を引いた数で、2 の値を持つビットがオフになり、1 が30個残ります。
発展問題
この関数が何百万回も実行される場合、256個の事前計算されたカウントを格納したテーブルを4回参照して、32ビット数のビット数を数えるにはどうすればよいでしょうか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
nの最後の2進数の桁だけを見ます。nを文字列に変換せずにその桁を読み取るにはどうすればよいでしょうか。また、次の桁を最後の位置に移動するにはどうすればよいでしょうか。n & 1（またはn % 2）は最後のビットで、1ビット右シフト（または2で割って切り捨て）すると取り除かれます。nが0になるまで、最後のビットを足し合わせます。より短いループには、
n & (n-1)を使います。これは、最下位の1ビットをオフにしたnです。nが0になるまでに何回適用できるか数えます。すると、ループは2進数の桁ごとではなく、1ビットごとに1回実行されます。
解説
文字列を作らずに、n の2進数の各桁を調べます。最後のビットを読み取ってシフトで取り除くには、2進数の各桁につき1ステップかかり、最大31ステップです。n & (n-1) で最下位の1ビットをクリアするには、1ビットにつき1ステップかかり、その回数は答えとちょうど同じです。
最後のビットを確認して右にシフトする
考え方
n & 1はnの最後の2進数の桁です。nが奇数なら1、偶数なら0になります。これをカウントに加えます。次に、n >> 1はその桁を取り除き、次の桁を最後の位置に移動します。非負数の場合、これは2で割って切り捨てることに相当します。11（1011）の場合、nが0になるまでに、最後のビットは1、1、0、1と読み取られます。つまり、1のビットは3つです。
ループはnが0になると停止するため、先頭のゼロは調べません。ステップ数は約log2(n)で、128の場合は8回、最大でも31回です。保存するのはnとカウントだけです。
アルゴリズム
- カウンターを0に設定します。
nが0より大きい間、n & 1をカウンターに加えます。nを1ビット右にシフトします。nが0になったら、カウンターを返します。
def hammingWeight(n):
count = 0
while n > 0:
count += n & 1 # the last bit is 1 or 0
n >>= 1 # drop the last bit
return countn & (n-1) で最下位のセットビットをクリアする
考え方
1を引くと、最も下位の1ビットが0に変わり、その下にあるすべての0が1に変わり、それより上位のビットは変わりません。つまり、n & (n-1)は上位のビットを保持し、最も下位の1ビットをクリアします。12は1100、11は1011で、1100 & 1011は1000です。
各ステップで1ビットがちょうど1つ取り除かれるので、nが0になるまでのステップ数が答えです。128なら8回ではなく1回で済みますが、2^31-1では依然として31回かかります。Lua 5.1にはビット演算子がないため、そのバージョンでは半分にして最も下位の1ビットを見つけ、それを引きます。ループは1ビットごとに1回実行されます。
アルゴリズム
- カウンターを0で初期化します。
nが0でない間、nをn & (n-1)に置き換えます。- 置き換えるたびに、カウンターに1を加えます。
- カウンターを返します。
def hammingWeight(n):
count = 0
while n != 0:
n &= n - 1 # turn off the lowest 1 bit
count += 1
return count
落とし穴と境界ケース
n > 1の間ループします。最後の 1 ビットの前にループが停止し、n = 1の場合は 0 を返します。- 浮動小数点数で割ります。JavaScript、Lua、R では、
11 / 2は 5.5 になり、その後の余りは分数になります。Math.floor、math.floor、%/%で切り捨てるか、代わりにシフトしてください。 - Lua 5.1 で
n & 1と書きます。ビット演算子がないため、コードはコンパイルできません。代わりにn % 2とmath.floor(n / 2)を使ってください。
よくある質問3
Number of 1 Bits の時間計算量は何ですか？
シフトループは2進数の各桁につき1回実行されます：O(log n)で、ここでは最大31ステップです。n & (n-1)のループは1ビットごとに1回実行されます：O(k)で、kは答えです。どちらも追加の領域はO(1)です。
セットビットを数える組み込み関数はありますか？
ほとんどの言語にはこの機能があり、多くの場合、単一のプロセッサ命令によって実装されています。Java の Integer.bitCount、GCC の __builtin_popcount、Go の bits.OnesCount、Rust の count_ones、そして Python 3.10 以降の int.bit_count です。面接では、ループを書いて、組み込み機能についても触れましょう。
ハミング重みとハミング距離の違いは何ですか？
数値のハミング重みとは、その2進数表現に含まれる1の数であり、この問題が返す値です。2つの数値のハミング距離とは、異なるビット位置の数です。XORは異なる位置だけを1にするため、a ^ b の1ビットの数を数えます。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def hammingWeight(n):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
n = 11
期待される出力
3