Follow

Follow

# LeetCode Solution, Easy, 67. Add Binary

·May 8, 2022·

## 題目敘述

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

Example 1:

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

Example 2:

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

Constraints:

• `1 <= a.length, b.length <= 10**4`
• `a` and `b` consist only of `'0'` or `'1'` characters.
• Each string does not contain leading zeros except for the zero itself.

## 解法解析

### Bit-by-Bit Computation

`N``M` 分別是 `a``b` 的字串長度 時間複雜度：`O(max(N,M))` 空間複雜度：`O(max(N,M))`

### Bit Manipulation

`N``M` 分別是 `a``b` 的字串長度 時間複雜度：`O(N+M)` 空間複雜度：`O(max(N,M))`

### 解法範例

#### Bit-by-Bit Computation

``````func addBinary(a string, b string) string {
i, j, res, carry := len(a)-1, len(b)-1, "", 0
for i >= 0 || j >= 0 {
if i >= 0 {
carry += int(a[i] - '0')
i--
}
if j >= 0 {
carry += int(b[j] - '0')
j--
}
res = strconv.Itoa(carry%2) + res
carry /= 2
}
if carry == 1 {
return "1" + res
}
return res
}
``````
##### Bit Manipulation
``````func addBinary(a string, b string) string {
var x, _ = new(big.Int).SetString(a, 2)
var y, _ = new(big.Int).SetString(b, 2)

var sum = new(big.Int)
var carry = new(big.Int)
for y.Text(2) != "0" {
sum.Xor(x, y)
carry.And(x, y).Lsh(carry, 1)
x.Set(sum)
y.Set(carry)
}
return x.Text(2)
}
``````

#### Bit-by-Bit Computation

``````/**
* @param {string} a
* @param {string} b
* @return {string}
*/
var addBinary = function (a, b) {
const N = a.length,
M = b.length;
let r = '';
let carry = false;
for (let i = 0; i < Math.max(N, M); i++) {
const da = a[N - i - 1] === '1',
db = b[M - i - 1] === '1';

const sum = (da !== db) !== carry;
r += (sum ? '1' : '0');
carry = (da && carry) || (db && carry) || (da && db);
}

return carry ? `1\${r}` : r;
};
``````
##### Bit Manipulation
``````/**
* @param {string} a
* @param {string} b
* @return {string}
*/
var addBinary = function (a, b) {
return (BigInt(`0b\${a}`) + BigInt(`0b\${b}`)).toString(2);
};
``````

#### Kotlin

``````
``````

#### Bit-by-Bit Computation

``````class Solution
{

/**
* @param String \$a
* @param String \$b
* @return String
*/
{
\$n = max(strlen(\$a), strlen(\$b));
\$carry = 0;
for (\$i = \$n - 1; \$i >= 0; \$i--) {
if (\$a[\$i] == '1') {
\$carry++;
}
if (\$b[\$i] == '1') {
\$carry++;
}

\$carry = floor(\$carry / 2);
}

if (\$carry == 1) {
}
}
}
``````
##### Bit Manipulation
``````
``````

#### Bit-by-Bit Computation

``````class Solution:
def addBinary(self, a: str, b: str) -> str:
n = max(len(a), len(b))
a, b = a.zfill(n), b.zfill(n)

carry = 0
for i in range(n - 1, -1, -1):
if a[i] == '1':
carry += 1
if b[i] == '1':
carry += 1

carry //= 2

if carry == 1:
``````
##### Bit Manipulation
``````class Solution:
def addBinary(self, a: str, b: str) -> str:
x, y = int(a, 2), int(b, 2)
while y:
x, y = x ^ y, (x & y) << 1
return bin(x)[2:]
``````

#### Rust

``````
``````

#### Swift

``````
``````