LeetCode 67 - Add Binary

https://leetcode.com/problems/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"

X.
1. followup是再给个base 参数
2. 2.Add Two Numbers 445. Add Two Numbers II
3. ⾯面试官问了了⼀一下问什什么不不能把string转换成integer，相加后，再转换成
⼆二进制 String。 想了了⼀一下，答道精度问题，如果输⼊入的⻓长度是100位，那
么Long和 Integer都装不不下。
4. 最后要求优化到使⽤用位运算

https://leetcode.com/problems/add-binary/discuss/24488/Short-AC-solution-in-Java-with-explanation
Computation from string usually can be simplified by using a carry as such.

    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();
    }

X.
https://leetcode.com/problems/add-binary/discuss/24524/Simple-accepted-java-solution
Addition bits are calculated by xor. Carry bit is calculated as simple integer addition.

    public String addBinary(String a, String b) {
        if(a == null || a.isEmpty()) {
            return b;
        }
        if(b == null || b.isEmpty()) {
            return a;
        }
        char[] aArray = a.toCharArray();
        char[] bArray = b.toCharArray();
        StringBuilder stb = new StringBuilder();

        int i = aArray.length - 1;
        int j = bArray.length - 1;
        int aByte;
        int bByte;
        int carry = 0;
        int result;

        while(i > -1 || j > -1 || carry == 1) {
            aByte = (i > -1) ? Character.getNumericValue(aArray[i--]) : 0;
            bByte = (j > -1) ? Character.getNumericValue(bArray[j--]) : 0;
            result = aByte ^ bByte ^ carry;
            carry = ((aByte + bByte + carry) >= 2) ? 1 : 0;
            stb.append(result);
        }
        return stb.reverse().toString();
    }

https://github.com/mintycc/OnlineJudge-Solutions/blob/master/Leetcode/002_Add_Two_Numbers.java

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(0);
        ListNode tail = head;
        int carry = 0;
        while (l1 != null || l2 != null) {
            int tmp = carry;
            if (l1 != null) {
                tmp += l1.val;
                l1 = l1.next;
            }
            if (l2 != null) {
                tmp += l2.val;
                l2 = l2.next;
            }
            carry = tmp / 10;
            tail.next = new ListNode(tmp % 10);
            tail = tail.next;
        }
        if (carry > 0) 
            tail.next = new ListNode(carry);
        return head.next;
    }

http://massivealgorithms.blogspot.com/2016/10/leetcode-445-add-two-numbers-ii.html