解答と解説: Hamming Distance

「問題演習: Hamming Distance」の解答編です。

解答例

Javaでの解答例です。

解答例１）

	public class Solution {
	public int hammingDistance(int x, int y) {
	int count = 0;
	while (x > 0 || y > 0) {
	count += (x & 1) ^ (y & 1);
	x >>>= 1;
	y >>>= 1;
	}
	return count;
	}
	}

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

解答例２）

	public class Solution {
	public int hammingDistance(int x, int y) {
	return Integer.bitCount(x ^ y);
	}
	}

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

解説

問題文から直感的に思いつくのは、解答例１の方法だと思います。この解法では、x と y から 1 ビットずつ取り出し、XOR（排他的論理和）が 1 になる場合、count に 1 を追加します。これを 1 ビットずつずらし、両方の値が 0 になるまで続けます。ただし、ビットをシフトするときは、シフト後に 0 が挿入される符号なしシフト演算子 ">>>" を使いましょう。左端のビットが 1 のとき、符号ありシフト演算子 ">>" を用いると、シフト後の左のビットには 1 が挿入されてしまい、ループが終わりません。注意しましょう。

類似の解法として、まず初めに x と y の XOR を取得した後に 1 ビットずつ調べる解法も良いと思います。例えば次のようなプログラムになります。

	public class Solution {
	public int hammingDistance(int x, int y) {
	int count = 0;
	int tmp = x ^ y;
	while (tmp > 0) {
	count += tmp & 1;
	tmp >>>= 1;
	}
	return count;
	}
	}

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

続いて解答例２ですが、以前「Power of Two の解答と解説」で Integer.bitCount(int n) というメソッドが用意されていることを紹介したのを覚えていますでしょうか。このメソッドは整数 n を 2 進数で表現したとき、ビットが 1 となる回数を返します。これを今回の問題で用いるには、まず x と y の XOR を取得した後、Integer.bitCount を用いることでビットが 1 の数を取得することができます。

以上が今回の解説になります。

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