题目

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:

  1. Input: a = "11", b = "1"
  2. Output: "100"

Example 2:

  1. Input: a = "1010", b = "1011"
  2. Output: "10101"

题意

实现以字符串表示的二进制加法。

思路

直接从后往前按位相加即可。

代码实现

Java

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

JavaScript

  1. /**
  2.  * @param {string} a
  3.  * @param {string} b
  4.  * @return {string}
  5.  */
  6. var addBinary = function (a, b) {
  7.   let i = 0
  8.   let carry = 0
  9.   let ans = []
  10.   while (i < a.length || i < b.length) {
  11.     let sum = carry
  12.     sum += i < a.length ? +a[a.length - 1 - i] : 0
  13.     sum += i < b.length ? +b[b.length - 1 - i] : 0
  14.     carry = Math.trunc(sum / 2)
  15.     sum %= 2
  16.     ans.unshift(sum)
  17.     i++
  18.   }
  19.   if (carry) {
  20.     ans.unshift(carry)
  21.   }
  22.   return ans.join('')
  23. }