二进制求和

描述

leetcode 官方第 67 题。给你两个二进制字符串，返回它们的和（用二进制表示）。输入为非空字符串且只包含数字 1 和 0。

示例1:

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

示例2:

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

提示：

• 每个字符串仅由字符 ‘0’ 或 ‘1’ 组成。
• 1 <= a.length, b.length <= 10^4。
• 字符串如果不是 “0” ，就都不含前导零。

思路

我们一般的情况下对十进制求和比较熟悉，其实二进制求和与十进制求和是类似的，十进制求和是遇 10 进 1。二进制求和是遇 2 进 1。我们可以从右往左遍历二进制数值，然后将每个遍历到的数据进行相加。

例如 11 + 1 ：

就算是十进制数据，我们是从右往左逐位相加。因为逢 2 需要进 1 位。所以 1 + 1 = 2，要转换为 0。并且将前一位进 1。前一位数据进行相加操作的时候，需要再额外加 1。

计算顺序如下：

• 第一步：1 + 1 =2。需要将当前的值设置为 0，并且将前一位是否需要加 1 的临时字段设置为 1。
• 第二部：1 + 0 + 1 = 2。当前第一个二进制数是 1。第二个二进制数没有值，就相当于 0。由于前一位相加之和是 2。需要前进一位，所以当前值需要加 1。计算结果为 2，需要将 2 转换成 0。将额外相加的临时值设置为 1。
• 判断额外相加的值是否为 1，如果是 1 就将 1 加上，如果不为 1 就结束。
• 将现有结果反转，得到最终数据。

例如 1010 + 1011:

和上面的步骤类型，要从右往左计算对应位置上面的和。因为逢 2 进 1。所以我们需要定义一个中间临时值，用来标记当前操作的时候是否需要再额外加 1。

计算顺序如下：

• 第一步：0 + 1 = 1。
• 第二步：1 + 1 = 2 ，转换成 0，在前一位相加是否需要额外加 1 的值赋值为 1。
• 第三步：0 + 0 + 1 = 1。
• 第四步：1 + 1 =2，转换为 0，在前一位相加是否需要额外加 1的值赋值为 1。
• 第五步：判断额外相加的值是否为 1，如果是 1 就将 1 加上，如果不为 1 就结束。
• 第六步：将现有结果反转，得到最终数据。

代码具体实现

Java语言版本

/**
 *逢2进1
 */
class Solution {
    public String addBinary(String a, String b) {
        char[] aarray = a.toCharArray();
        char[] barray = b.toCharArray();
         int alength = aarray.length;
        int blength = barray.length;
        int maxLength = (alength > blength ? alength : blength);
        int currentAvalue = 0;
        int currentBvalue = 0;
        //记录是否上一次相加操作大于 2 ，当前操作是否要加 1
        int tmpValue = 0;
        //记录遍历 a 数组的位置
        int aCurrentIndex = alength - 1;
        //记录遍历 b 数组的位置
        int bCurrentIndex = blength - 1;
        //用来接受返回值
        StringBuffer retStrBuffer = new StringBuffer(); 
        for (int i = 0; i < maxLength; i++) {
            if (aCurrentIndex >= 0) {
                //因为 char 类型的数据会被转换成 ASCII 码，所以减去 ‘0’
                currentAvalue = aarray[aCurrentIndex] - '0';
                aCurrentIndex--;
            } else {
                currentAvalue = 0;
            }
            if (bCurrentIndex >= 0) {
                currentBvalue = barray[bCurrentIndex] - '0';
                bCurrentIndex--;
            } else {
                currentBvalue = 0;
            }
            int tmpTotalValue = (currentBvalue + currentAvalue + tmpValue);
            if (tmpTotalValue >= 2) {
                //逢 2 进 1
                tmpTotalValue = tmpTotalValue - 2;
                tmpValue = 1;
            } else {
                tmpValue = 0;
            }
            retStrBuffer.append(tmpTotalValue);
        }
        if (tmpValue == 1) {
            //因为追加的时候是从最右侧开始追加，所以需要将字符串反转
            return  "1" + retStrBuffer.reverse().toString();
        }
        //因为追加的时候是从最右侧开始追加，所以需要将字符串反转
        return retStrBuffer.reverse().toString();
    }
}

Go语言版本

func addBinary(a string, b string) string {
    a = reverse(a)
    b = reverse(b)
    var(
        aByte = []byte(a)
        bByte = []byte(b)
        aLength = len(aByte)
        bLength = len(bByte)
        maxLength = If(aLength > bLength , aLength , bLength).(int)
        currentAvalue = 0
        currentBvalue = 0
        //记录是否上一次相加操作大于 2 ，当前操作是否要加 1
        tmpValue = 0
    )
    //记录遍历 a 数组的位置
    aMaxIndex := aLength - 1
    //记录遍历 b 数组的位置
    bMaxIndex := bLength - 1
    //var retStrBuffer bytes.Buffer
    var retStr string
    for i := 0; i < maxLength; i++ {
        if i <= aMaxIndex {
            //因为 char 类型的数据会被转换成 ASCII 码，所以减去 ‘0’
            currentAvalue = int(aByte[i]) - int('0')
        }else {
            currentAvalue = 0
        }
        if i <= bMaxIndex {
            currentBvalue = int(bByte[i]) - int('0')
        } else {
            currentBvalue = 0
        }
        var tmpTotalValue = currentBvalue + currentAvalue + tmpValue
        if tmpTotalValue >= 2 {
            //逢 2 进 1
            tmpTotalValue = tmpTotalValue - 2
            tmpValue = 1
        } else {
            tmpValue = 0
        }
        retStr += strconv.Itoa(tmpTotalValue)
    }
    if tmpValue == 1 {
        retStr += strconv.Itoa(1)
    }
    return reverse(retStr)
}
//三木运算符效果
func If(condition bool, trueVal, falseVal interface{}) interface{} {
    if condition {
        return trueVal
    }
    return falseVal
}
//数据反转函数
func reverse( str string ) string {
    r := []rune(str)
    for i, j := 0, len(r)-1; i < j; i, j = i+1, j-1 {
        r[i], r[j] = r[j], r[i]
    }
    return string(r)
}