67. 二进制求和

发表于 更新于 分类于 ，

题目

给定两个二进制字符串，返回他们的和（用二进制表示）。

输入为非空字符串且只包含数字 1 和 0。

示例 1:

1
2
输入: a = "11", b = "1"
输出: "100"

示例 2:

1
2
输入: a = "1010", b = "1011"
输出: "10101"

思路

又是字符串相加的题目,思路类似于上一题的数组加法,只要是要自己实现加法的,步骤都基本如下:

  • 定义一个进位变量flag.
  • 如果长度不一致,将两者长度变成一致.
  • 从右到左按位相加,如果产生了进位,进位就变成1.
  • 循环结束后,如果flag仍为1,则说明还要加一.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public string AddBinary(string a, string b)
{
    if (a.Length > b.Length)
    {
        b = b.PadLeft(a.Length, '0');//用padleft这个方法来填充0.
    }
    else
    {
        a = a.PadLeft(b.Length, '0');
    }
    int flag = 0;
    string result = "";
    for (int i = a.Length - 1; i >= 0; i--)
    {
        result = (((int)a[i] - 48 + (int)b[i] - 48 + flag) % 2).ToString() + result;
        flag = ((int)a[i] - 48 + (int)b[i] - 48 + flag) / 2;
    }
    return flag == 1 ? flag + result : result;
}