67. Add Binary

Given two binary strings, return their sum (also a binary string).

For example,
a = “11”
b = “1”
Return “100”.

思路:
从右往左挨个比较,进行二进制的数值计算。把每位获得的值放到StringBuffer里面,最后检查carry是否为1,并reverse,最后以String返回。

public class Solution {
    public String addBinary(String a, String b) {
        if (a == null || a.length() == 0) return b;
        if (b == null || b.length() == 0) return a;

        StringBuilder sb = new StringBuilder();
        int carry = 0;
        int alen = a.length() - 1;
        int blen = b.length() - 1;
        for (int ia = alen, ib = blen; ia >= 0 || ib >= 0; ia--,ib--) {
            int aNum = ia < 0 ? 0 : a.charAt(ia) - '0';
            int bNum = ib < 0 ? 0 : b.charAt(ib) - '0';
            int sum = aNum + bNum + carry;
            int digit = sum % 2;
            sb.append(digit);
            carry = sum / 2;
        }
        if (carry == 1) {
            sb.append('1');
        }
        sb.reverse();
        return sb.toString();
    }
}

注意点:

  • 如何从char转化为对应的数字? 可以char的值跟’a’, ‘A’, ‘0’做减法
  • 处理String做运算的题目可以考虑是否能用StringBuilder, 依次把计算的数值放进去,最后reverse。
  • 二进制carry的情况,最后别忘了检查carry是否为1. 如果为1,则要进位。

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s