解答と解説: Hamming Weight

「問題演習: Hamming Weight」の解答編です。模範解答に加え、Java が提供している便利なメソッドを使った解答を用意しました。

解答例

Javaでの解答例です。

解答例１）

	public class Solution {
	public int hammingWeight(int n) {
	int count = 0;
	while (n != 0) {
	if ((n & 1) == 1) {
	count++;
	}
	n >>>= 1;
	}
	return count;
	}
	}

view raw hamming-weight.java hosted with ❤ by GitHub

解答例２）

	public class Solution {
	public int hammingWeight(int n) {
	return Integer.bitCount(n);
	}
	}

view raw hamming-weight.java hosted with ❤ by GitHub

解説

模範解答である解答例１について解説する前に、解答例２の解法について簡単に述べます。この解法では、以前「Power of Two の解答と解説」と「Hamming Distance の解答と解説」で紹介した Integer.bitCount(int n) というメソッドを用いています。繰り返しになりますが、このメソッドは整数 n を 2 進数で表現したとき、ビットが 1 となる回数を返します。つまり、このメソッドに整数を渡せばハミング重みが求まります。

解答例１は、整数 n の最下位の 1 ビットを取り出し、それが 1 のときに count をインクリメントしています。そして整数 n を 1 ビットずつ右にづらし、n が 0 になるまで繰り返します。ここまでは特に注意することはありません。

前回の問題出題時に「与えられる整数は正の整数であると問題文に指定されています。左端のビットが 1 である整数は負数をして扱っていないか注意してください。」と述べました。C 言語のように unsigned 修飾子を用いることによって正の整数を宣言することができますが、Java にはそのような修飾子はありません。そのため、特に特別な処理をしなければ Java では左端のビットが 1 の整数は符号あり整数、つまり負の整数になります。今回の問題では、これを符号なし整数、つまり常に正の整数として扱う必要があります。それでは Java でプログラムを記述する際に注意すべき点を 2 点挙げます。

1 つ目の注意点は、整数 n を右にシフトするとき、解答例１のように符号なしシフト演算子 ">>>" を用いることです。符号なしシフト演算子を用いると左端のビットが 1 の整数に対しても、シフト後に左端に 0 が挿入されます。一方、左端のビットが 1 の整数に符号ありシフト演算子 ">>" を用いると、シフト後は左端に 1 が挿入されてしまいます。これを 1 がなくなるまでループするようなプログラムは無限ループになってしまいますので、気をつけましょう。

２つ目の注意点は 4 行目のループの記述についてです。解答例１では "while (n != 0)" のように "0 でなければループを回る" と記述しています。この部分は "while (n > 0)" のように "n が 0 より大きければループを回る"という記述では不正解です。その理由は、我々は整数 n を符号なし整数として扱っているつもりですが、Java では n は符号あり整数として扱われるため、整数 n の先頭の 1 ビットが 1 の場合は負数、つまり n は 0 より小さいと判断され、ループの中に入ることができません。そのため、解答例１のように n が 0 でないときにループを回るような条件文にする必要があります。

以上が今回の解説になります。
---
シリコンバレーでエンジニアとして就職するには、アルゴリズムやプログラミング、システムデザインの問題が出題される面接を突破する必要があります。本サイトでは、シリコンバレーでエンジニアとして働き、面接官としての経験も豊富な筆者が、面接への対策に関する情報を配信しています。