アルゴリズムの説明:32 ビット符号付き整数のセット ビットのカウント

問題文:32 ビットの符号付き整数が与えられたとき、セットされたビットはいくつありますか?

例:数値 15 には 4 つのビットが設定されています。

この記事では、この問題にどのようにアプローチするかを説明します。

アプローチ

ビットが設定されているかどうかはどうすればわかりますか?

ビットは 0 または 1 のいずれかです。値が 1 の場合、ビットは設定されます。

整数に設定されているビット数を知るには、整数のバイナリ表現を調べて、1 に等しいビット数をカウントする必要があります。

これは 15 の 32 ビット バイナリ表現です:

00000000 00000000 00000000 00001111Code language: plaintext (plaintext)

これには 4 つのセット ビットがあります。これを見ればわかります。

ビットがプログラムで設定されているかどうかはどうすればわかりますか?

ビットマスクでビットごとの AND (&) 演算子を使用できます。

2 つのビットの AND をとった場合、両方のビットが 1 の場合にのみ結果が 1 になります:

1 & 1 = 1
1 & 0 = 0
0 & 1 = 0
0 & 0 = 0Code language: plaintext (plaintext)

&演算子は、2 つの数値の各位置の AND をとります。結果は、両方の数値で設定された場所のみにビットが設定された数値です。

したがって、最初のビットが設定されているかどうかを確認するには、最初のビットが設定されたビットマスクを使用し、結果の数値がビットマスクと等しいかどうかを確認します:

  00000000 00000000 00000000 00001111
& 00000000 00000000 00000000 00000001 (bitmask)
------
= 00000000 00000000 00000000 00000001Code language: plaintext (plaintext)

結果の数値はビットマスクと等しいため、最初のビットが別の数値に設定されていることがわかります。

32 ビットすべてを確認するにはどうすればよいですか?

最初のビットをチェックするには、最初のビットが設定されたビットマスクを使用します。 2 番目のビットを確認するには、2 番目のビットが設定されたビットマスクを使用します。等々。

つまり、次のように 32 個のビットマスクを作成します。

Position 1  00000000 00000000 00000000 00000001
Position 2  00000000 00000000 00000000 00000010
...
Position 32 10000000 00000000 00000000 00000000Code language: plaintext (plaintext)

ビットマスクをインクリメントするには、ビットごとの LEFT-SHIFT (<<) 演算子を使用できます。

これにより、ビットが指定されたカウントだけ左にシフトされます。

  0001
<<   1             
------
= 0010Code language: plaintext (plaintext)

符号付き整数を右シフトしない

整数を右シフトしてビットマスク 1 との AND を続けることはできませんか?

いいえ

整数は符号付きです。つまり、負になる可能性があります。負の整数の右シフトは、正の整数の右シフトと同じようには機能しません。単純にビットを 1 右に移動する代わりに、ビットを 1 右に移動してから、左のビットを 0 で埋めます。

たとえば、この負の数を 1 だけ右シフトしています:

  1000
>>   1             
------
= 1100Code language: plaintext (plaintext)

これが正の整数の場合と同じように機能する場合、結果は 0100 になります。ただし、左側のビットが 1 で埋められるため、結果は代わりに 1100 になります。これが、セットされたビットを数えようとしている場合、符号付き整数を右シフトしてはならない理由です。

テストケース

この問題を解決する方法がわかったので、テスト ケースを作成します。基本ケース (0 と 1)、手動で検証できるランダム ケース (15)、およびエッジ ケース (最小および最大 int32) を組み合わせるのが好きです。

入力 期待値
0 0
1 1
15 4
最大 int32
2,147,483,647
31
最小 int32
-2,147,483,648
1

コード

public int CountSetBits(int number)
{
	int count = 0;
	int mask = 1;
	for (int i = 0; i < 32; i++)
	{
		if ((mask & number) == mask)
			count++;
		mask = mask << 1;
	}
	return count;
}
Code language: C# (cs)