Add Binary（二进制求和）

题目 / Problem

中文： 给定两个二进制字符串 a 和 b，返回它们的和，结果也使用二进制字符串表示。

English: Given two binary strings a and b, return their sum as a binary string.

示例 / Examples

Example 1

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

  11
+ 01
----
 100

Example 2

Input:  a = "1010", b = "1011"
Output: "10101"

  1010
+ 1011
------
 10101

约束 / Constraints

• 1 <= a.length, b.length <= 10⁴
• a 和 b 只包含字符 '0' 或 '1'。
  a and b consist only of '0' and '1' characters.
• 除了字符串 "0" 本身，每个字符串都不包含前导零。
  Neither string contains leading zeros except for "0" itself.

解题思路：模拟二进制竖式加法 / Approach: Simulate Binary Addition

二进制加法与十进制竖式加法相同，需要从最低位向最高位逐位计算，并保存进位。
Binary addition works like decimal column addition: process digits from right to left while carrying into the next position.

使用以下变量：
Use the following variables:

• i：指向字符串 a 的当前位，从末尾开始。
  i: points to the current digit of a, starting at the end.
• j：指向字符串 b 的当前位，从末尾开始。
  j: points to the current digit of b, starting at the end.
• carry：当前进位，只可能是 0 或 1。
  carry: the current carry, which can only be 0 or 1.
• result：保存从低位到高位得到的结果数字。
  result: stores result digits generated from least significant to most significant.

每一轮计算：
In every iteration:

sum = 当前 a 的数字 + 当前 b 的数字 + carry
当前结果位 = sum % 2
新的进位 = Math.floor(sum / 2)

如果某个字符串已经遍历完，就将它当前位的值视为 0。当两个字符串都遍历完且 carry === 0 时，计算结束。
If one string has been exhausted, treat its current digit as 0. The calculation ends when both strings are exhausted and carry === 0.

由于结果是从低位向高位产生的，最后需要将结果数组反转。
Because result digits are generated from right to left, reverse the result array at the end.

JavaScript 实现 / JavaScript Implementation

/**
 * @param {string} a
 * @param {string} b
 * @return {string}
 */
function addBinary(a, b) {
  const result = [];
  let i = a.length - 1;
  let j = b.length - 1;
  let carry = 0;

  while (i >= 0 || j >= 0 || carry > 0) {
    const digitA = i >= 0 ? a.charCodeAt(i) - 48 : 0;
    const digitB = j >= 0 ? b.charCodeAt(j) - 48 : 0;
    const sum = digitA + digitB + carry;

    result.push(sum % 2);
    carry = Math.floor(sum / 2);

    i--;
    j--;
  }

  return result.reverse().join('');
}

ASCII 中字符 '0' 的编码为 48，因此 charCodeAt(index) - 48 可以将字符 '0'、'1' 转换为数字 0、1。
The ASCII code for '0' is 48, so charCodeAt(index) - 48 converts '0' and '1' into the numbers 0 and 1.

也可以使用 Number(a[i]) 转换字符，但 charCodeAt() 避免了每一位的通用数值转换。
Number(a[i]) could also convert each character, but charCodeAt() avoids a general numeric conversion for every digit.

执行过程 / Walkthrough

以 a = "1010"、b = "1011" 为例，从右向左计算：
For a = "1010" and b = "1011", calculate from right to left:

结果位的产生顺序为 [1, 0, 1, 0, 1]。反转后仍为 [1, 0, 1, 0, 1]，最终返回 "10101"。
The result digits are generated as [1, 0, 1, 0, 1]. Reversing them happens to produce the same sequence, so the final result is "10101".

再看 a = "11"、b = "1"：
For a = "11" and b = "1":

低位到高位得到 [0, 0, 1]，反转后为 [1, 0, 0]，返回 "100"。
The digits produced from right to left are [0, 0, 1]. After reversal, they become [1, 0, 0], so return "100".

二进制加法规则 / Binary Addition Rules

无论 sum 是 0、1、2 还是 3，都可以统一使用 % 2 得到当前位，使用除以 2 向下取整得到进位。
Whether sum is 0, 1, 2, or 3, % 2 gives the current digit and integer division by 2 gives the carry.

复杂度 / Complexity

设 n = max(a.length, b.length)。
Let n = max(a.length, b.length).

• 时间复杂度：O(n)，每一位只处理一次，最后反转结果也需要 O(n)。
  Time: O(n), because every digit is processed once and reversing the result also takes O(n).
• 空间复杂度：O(n)，结果数组最多保存 n + 1 位。
  Space: O(n), because the result array stores at most n + 1 digits.

不计算必须返回的结果字符串时，辅助变量只占 O(1) 空间。
Excluding the required output string, the scalar helper variables use O(1) space.

为什么不能直接转换为 Number？ / Why Not Convert Directly to Number?

字符串长度最多为 10⁴，远远超过 JavaScript Number 能够精确表示的整数范围。直接使用 parseInt(a, 2) + parseInt(b, 2) 会产生精度丢失，甚至得到 Infinity。
The strings may contain up to 10⁴ digits, far beyond the exact integer range of JavaScript's Number. Using parseInt(a, 2) + parseInt(b, 2) can lose precision or even produce Infinity.

逐位模拟加法不依赖整数大小，能够正确处理题目允许的所有输入。
Digit-by-digit simulation does not depend on the numeric magnitude and correctly handles every allowed input.

虽然 JavaScript 的 BigInt 可以表示任意长度整数，但逐位模拟更符合本题考查目标，也适用于没有大整数支持的语言。
Although JavaScript's BigInt supports arbitrary-size integers, digit-by-digit simulation better matches the problem's purpose and works in languages without big integers.

易错点 / Common Pitfalls

• 必须从字符串末尾开始相加，因为末尾是二进制最低位。
  Add from the ends of the strings because they contain the least significant bits.
• 两个字符串长度可能不同，较短字符串缺失的位置应视为 0。
  The strings may have different lengths; missing positions in the shorter one should be treated as 0.
• 两个字符串处理完后，仍需检查是否存在最后的进位。
  After both strings are exhausted, check for a final carry.
• 结果位按从低到高的顺序产生，返回前需要反转。
  Result digits are generated from least to most significant, so reverse them before returning.
• 不要将整个输入转换为 JavaScript Number，长字符串会超出安全整数范围。
  Do not convert the complete inputs to JavaScript Number; long strings exceed its safe integer range.
• sum % 2 得到当前位，Math.floor(sum / 2) 得到下一位进位。
  Use sum % 2 for the current digit and Math.floor(sum / 2) for the next carry.