模拟竖式加法即可

有两个重要的公式：

  1. // 求当前位的值
  2. cur = (carry + a(i) + b(i)) % 2 （十进制就余10）
  4. // 进位
  5. carry = (carry + a(i) + b(i)) / 2
  1. class Solution {
  2.     public String addBinary(String a, String b) {
  3.         if (a == null && a.length() == 0 && b == null && b.length() == 0) return "";
  4.         if (a == null || b == null) return a == null ? b : a;
  5.         StringBuilder sb = new StringBuilder();
  6.         int len = Math.max(a.length(), b.length());
  7.         int carry = 0, aL = a.length() - 1, bL = b.length() - 1;
  9.         // 从后往前
  10.         // 计算当前位的值：cur = (carry + a.charAt(i) + b.charAt(i)) % 2;
  11.         // 计算进位：(carry + a.chat(i) + b.chatAt(i)) / 2
  12.         // 
  13.         for (int i = 0; i < len; i++) {
  14.             int res = carry;
  15.             if (i < a.length()) {
  16.                 res += a.charAt(aL - i) - '0';
  17.             }
  18.             if (i < b.length()) {
  19.                 res += b.charAt(bL - i) - '0';
  20.             }
  21.             carry = res / 2;
  22.             res %= 2;
  23.             sb.append(res);
  24.         }
  25.         if (carry != 0) sb.append(carry);
  27.         return sb.reverse().toString();
  28.     }
  29. }