解答と解説: Add Binary Strings

「問題演習: Add Binary Strings」の解答編です。この問題のポイントとしては、文字列で表記された 2 進数を最下位のビットから計算する際に桁上げ処理を忘れずに行うことです。それでは解答例を見ていきましょう。

解答例

Javaでの解答例です。

	public class Solution {
	public String addBinaryStrings(String s1, String s2) {
	String s = "";
	int s1len = s1.length();
	int s2len = s2.length();
	int mlen = Math.max(s1len, s2len);
	int count = 0;
	for (int i = 0; i < mlen; i++) {
	if (s1len > i) {
	count += s1.charAt(s1len - 1 - i) - '0';
	}
	if (s2len > i) {
	count += s2.charAt(s2len - 1 - i) - '0';
	}
	s = ((char) (count % 2 + '0')) + s;
	count /= 2;
	}
	if (count > 0) {
	s = '1' + s;
	}
	return s;
	}
	}

view raw add-binary-strings.java hosted with ❤ by GitHub

解説

7 行目で count という int 型の変数を用意しています。この変数は与えられた 2 つの 2 進数を走査するとき、各桁においてビットが 1 となる数を保持します。つまり、 1 つの 2 進数のi 番目の桁が 1 のとき、count に 1 を追加します。もう一方の 2 進数についても同様です。また、2 つの 2 進数の両方とも i - 1 番目の桁が 1 だった場合、i 番目のビットは 1 を加える必要があるため、count に 1 を追加します。

この処理を行うことで、下記のように最終的に求める 2 進数の各桁の値と桁上げ処理の有無を判断することができます。

• count=0 のとき、i 番目のビットは 0 となり、桁上げは行わない。
• count=1 のとき、i 番目のビットは 1 となり、桁上げは行わない。
• count=2 のとき、i 番目のビットは 0 となり、桁上げを行う。
• count=3 のとき、i 番目のビットは 1 となり、桁上げを行う。

つまり、count の値が 2 で割り切れるときは i 番目のビットは 0、そうでないときは 1 なので、15 行目のように "count % 2 + '0'" と記述することができます。また、count の値が 2 より大きい時に桁上げを行う必要があります。この処理は 16 行目のように "count /= 2" で行うことができます。

また、最後の桁を走査し終えてループを抜けた後も、最後の桁で桁上げが発生した場合には count の値に 1 が入っているはずです。そのための処理は 18 行目で行っています。

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