Add Binary

问题描述

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

For example,
a = "11"
b = "1"
Return "100".

算法

代码一

 1 public String addBinary(String a, String b) {
 2         int i = 0, length1 = a.length(), length2 = b.length();
 3         HashMap<String, String> map = new HashMap<String, String>();
 4         map.put("000", "00");
 5         map.put("001", "01");
 6         map.put("010", "01");
 7         map.put("011", "10");
 8         map.put("100", "01");
 9         map.put("101", "10");
10         map.put("110", "10");
11         map.put("111", "11");
12         String s = "0", result = "", value;
13         while (i < length1 && i < length2) {
14             s += a.charAt(length1 - 1 - i);
15             s += b.charAt(length2 - 1 - i);
16             value = map.get(s);
17             result += value.charAt(1);
18             s = value.substring(0, 1);
19             i++;
20         }
21         if (i >= length1) {
22             while (i < length2) {
23                 s += b.charAt(length2 - 1 - i);
24                 s += "0";
25                 value = map.get(s);
26                 result += value.charAt(1);
27                 s = value.substring(0, 1);
28                 i++;
29             }
30         } else {
31             while (i < length1) {
32                 s += a.charAt(length1 - 1 - i);
33                 s += "0";
34                 value = map.get(s);
35                 result += value.charAt(1);
36                 s = value.substring(0, 1);
37                 i++;
38             }
39         }
40         if(s.equals("1"))
41             result+=s;
42         return new StringBuilder(result).reverse().toString();
43     }

代码二

 1 public String addBinary1(String a, String b) {
 2         StringBuilder sb = new StringBuilder();
 3         int i = a.length() - 1, j = b.length() - 1, carry = 0;
 4         while (i >= 0 || j >= 0) {
 5             int sum = carry;
 6             if (j >= 0)
 7                 sum += b.charAt(j--) - '0';
 8             if (i >= 0)
 9                 sum += a.charAt(i--) - '0';
10             sb.append(sum % 2);
11             carry = sum / 2;
12         }
13         if (carry != 0)
14             sb.append(carry);
15         return sb.reverse().toString();
16 
17     }

注意事项：

（1）String s="sdhfowf";则s.charAt(0)=='s'。

（2）String变量没有反转函数，StringBuilder有反转函数。