Add Binary

Problem:

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

For example,

a = "11"

b = "1"

Return "100".

Analysis:

At the very beginning, I still didn't know where to start. Referenced [1], then I realized this is a simple problem. And decided to do it on my own. I implemented in Eclipse, debugged several rounds. Put the code to LeetCode online Jug, got accepted immediately.

The key of this problem is reverse the strings. Because we do math sum up from lower digit to higher digit right to left, but array index is from left to right.

Example:

 0 1 1 0 1
+     1 0 1 1 1
---------------------
=  1 0 0 1 0 0

The implementation of [1] seems a mass to me, so I did it in a more concise way. 

Solution:

1:  public static String addBinary(String a, String b)  
2:       {  
3:       StringBuilder asb=new StringBuilder(a);  
4:       StringBuilder bsb=new StringBuilder(b);  
5:       StringBuilder resB=new StringBuilder();  
6:       int length=Math.max(asb.length(), bsb.length());  
7:       int i=0;  
8:       int carry=0;  
9:       int digit1=0;  
10:       int digit2=0;  
11:       int digit3=0;  
12:       String resC = null;  
13:       asb.reverse();  
14:       bsb.reverse();  
15:       while(i<length)  
16:       {  
17:        digit1=i<asb.length()?asb.charAt(i)-'0':0;  
18:        digit2=i<bsb.length()?bsb.charAt(i)-'0':0;;  
19:        digit3=digit1+digit2+carry;  
20:       switch(digit3)  
21:       {  
22:        case 0:resC="0";  
23:           carry=0;  
24:           break;  
25:        case 1:resC="1";  
26:           carry=0;  
27:           break;  
28:        case 2:resC="0";  
29:           carry=1;  
30:           break;  
31:        case 3:resC="1";  
32:           carry=1;  
33:           break;  
34:       }  
35:       resB.append(resC);  
36:       i++;  
37:       }  
38:       if(carry>0)  
39:            resB.append("1");  
40:       resB.reverse();  
41:       return resB.toString();  
42:       }  

Reference:

[1] http://n00tc0d3r.blogspot.com/2013/01/add-two-binary-numbers.html?q=add