# Add Binary

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

The input strings are both **non-empty** and contains only characters`1`or `0`.

**Example 1:**

```
Input:
 a = "11", b = "1"

Output:
 "100"
```

**Example 2:**

```
Input:
 a = "1010", b = "1011"

Output:
 "10101"
```

## Analysis

Easy难度，但是有一些需要注意的点：

在计算过程不可以将a，b都转化为数（Integer/Long）来求和，因为测试样例和题中并没有限制数据的长度大小，因此会溢出导致错误。

返回String字符串，动态字符串可以用StringBuilder（或者StringBuffer，如果用多线程，因为StringBuffer是sync），减小字符串拼接时间复杂度 （O(n^2) - > O(n)）

从低位到高位的顺序进行相加求和，因此得到的StringBuilder是逆序，需要翻转后输出。

## Solution

Preferred Implementation - Binary Conversion

> Computation from string usually can be simplified by using a carry as such.

```java
public class Solution {
    public String addBinary(String a, String b) {
        StringBuilder sb = new StringBuilder();
        int i = a.length() - 1, j = b.length() -1, carry = 0;
        while (i >= 0 || j >= 0) {
            int sum = carry;
            if (j >= 0) sum += b.charAt(j--) - '0';
            if (i >= 0) sum += a.charAt(i--) - '0';
            sb.append(sum % 2);
            carry = sum / 2;
        }
        if (carry != 0) sb.append(carry);
        return sb.reverse().toString();
    }
}
```

Using Bit operation XOR

```java
public class Solution {
    public String addBinary(String a, String b) {
        if(a == null || a.isEmpty()) 
            return b;
        if(b == null || b.isEmpty()) 
            return a;


        StringBuilder stb = new StringBuilder();
        int i = a.length() - 1;
        int j = b.length() - 1;
        int aBit;
        int bBit;
        int carry = 0;
        int result;

        while(i >= 0 || j >= 0 || carry == 1) {
            aBit = (i >= 0) ? Character.getNumericValue(a.charAt(i--)) : 0;
            bBit = (j >= 0) ? Character.getNumericValue(b.charAt(j--)) : 0;
            result = aBit ^ bBit ^ carry;
            carry = ((aBit + bBit + carry) >= 2) ? 1 : 0;
            stb.append(result);
        }
        return stb.reverse().toString();
    }
}
```

错误方法会在数据较大时溢出从而导致错误：

Wrong Answer：

207 / 294 test cases passed.

```
Input:
"10100000100100110110010000010101111011011001101110111111111101000000101111001110001111100001101"
"110101001011101110001111100110001010100001101011101010000011011011001011101111001100000011011110011"
Output:
"11101000101011001000011011000001100011110011010010011000000000"
Expected:
"110111101100010011000101110110100000011101000101011001000011011000001100011110011010010011000000000"
```

Wrong Way：

```java
class Solution {
    public String addBinary(String a, String b) {
        char[] chA = a.toCharArray();
        char[] chB = b.toCharArray();
        long longA = 0;
        long longB = 0;
        long numA = convertToLong(chA);
        long numB = convertToLong(chB);
        long sum = numA + numB;
        String s = convertToBinaryString(sum);
        return s;
    }
    private long convertToLong(char[] chs) {
        long num = 0;
        for (char ch : chs) {
            num = num << 1;
            num = num + ch - '0';
        }
        return num;   
    }

    private String convertToBinaryString(long num) {
        if (num == 0) {
            return "0";
        }
        List<String> strList = new ArrayList<String>(); 
        while (num > 0) {
            long tmp = num % 2;
            strList.add(Long.toString(tmp));
            num = num / 2;
        }

        Collections.reverse(strList);
        String str = String.join("", strList);
        return str;
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aaronice.gitbook.io/lintcode/string/add-binary.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.