67.二进制求和.md

67. 二进制求和

url

题目

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

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

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

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

方法

主要是考察进位

• 经常用到 x % 2 得到该数的最后一位数字
• 配合sum / 2 得到进位

code

js

let addBinary = (a, b) => {
    let i = a.length - 1;
    let j = b.length - 1;
    let carry = 0;
    let res = []
    while (carry === 1 || i >= 0 || j >=0) {
        if (i >= 0 && a[i--] === "1") carry++;
        if (j >= 0 && b[j--] === "1") carry++;
        res.push(carry % 2);
        carry = Math.floor(carry / 2);
    }
    return res.reverse().join("");
}

console.log(addBinary("11", "1"));
console.log(addBinary("1010", "1011"));

go

func addBinary(a, b string) string {
	reverseStr := func (s string) string {
		runes := []rune(s)
		for i, j := 0, len(runes) - 1; i < j; i, j = i + 1, j - 1 {
		runes[i], runes[j] = runes[j], runes[i]
	}
		return string(runes)
	}
	i, j, carry := len(a) - 1, len(b) - 1, 0
	var str []string
	for carry == 1 || i >= 0 || j >= 0 {
		if i >= 0 && a[i] == '1' {
			carry++
		}
		i--
		if j >= 0 && b[j] == '1' {
			carry++
		}
		j--
		str = append(str, strconv.Itoa(carry % 2))
		carry /= 2
	}
	return reverseStr(strings.Join(str, ""))
}

java

class Solution {
    public String addBinary(String a, String b) {
        int i = a.length() - 1, j = b.length() - 1, carry = 0;
        StringBuilder str = new StringBuilder();
        while (carry == 1 || i >= 0 || j >= 0) {
            if (i >= 0 && a.charAt(i--) == '1') carry++;
            if (j >= 0 && b.charAt(j--) == '1') carry++;
            str.append(carry % 2);
            carry /= 2;
        }
        return str.reverse().toString();
    }
}