Add Binary

只需要按顺序一个一个加即可,从最低位(最右边开始)。 如果某个数已经达到0,那么就按这一位是0算。用s1,s2,c表示两个加数和一个carry,最后如果carry是1的话,再最后加上一个1.


public class Solution {
    public String addBinary(String a, String b) {
        int l = Math.max(a.length(), b.length());
        int al = a.length() ;
        int bl = b.length() ;
        int s1 = 0, s2 = 0, c = 0, sum = 0;
        StringBuilder res = new StringBuilder();
        for (int i = l - 1; i >= 0; i--)
        {
            if ( al != 0 )
            {
                s1 = (a.charAt(al-1) == '0')? 0 : 1;
                al--;
            }
            else
                s1 = 0;
            if (bl != 0 )
            {
                s2 = (b.charAt(bl-1) == '0')? 0 : 1;
                bl--;
            }
            else
                s2 = 0;
            
            sum = s1 + s2 + c;
            c = (sum > 1)? 1 : 0;
            sum = sum & 0x1;
            res.insert(0, (sum == 0)? '0' : '1');
        }
        if (c == 1)
            res.insert(0, '1');
        return (new String(res));
    }
}

First Reverse the two input string, then we can start from 0 which makes the code more clean

public class Solution {
    public String addBinary(String a, String b) {
        if (a.length() == 0)
            return b;
        if (b.length() == 0)
            return a;
        int carry = 0;
        int index = 0;
        StringBuilder a1 = new StringBuilder(a);
        StringBuilder b1 = new StringBuilder(b);
        a1.reverse();
        b1.reverse();
        StringBuilder res = new StringBuilder();
        while(index < a1.length() && index < b1.length()) {
            int sum = (int)(a1.charAt(index) - '0') + (int)(b1.charAt(index) - '0') + carry;
            carry = sum/2;
            sum = sum%2;
            res.append((char)(sum + '0'));
            index++;
        }
        while (index < a1.length()) {
            int sum = (int)(a1.charAt(index) - '0') + carry;
            carry = sum/2;
            sum = sum%2;
            res.append((char)(sum + '0'));
            index++;
        }
        while (index < b1.length()) {
            int sum = (int)(b1.charAt(index) - '0') + carry;
            carry = sum/2;
            sum = sum%2;
            res.append((char)(sum + '0'));
            index++;
        }
        if (carry == 1) {
            res.append('1');
        }
        return new String(res.reverse());
    }
}

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