# LeetCode Solution, Easy, 67. Add Binary

# [67. Add Binary](https://leetcode.com/problems/add-binary/)

## 題目敘述

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.

### 題目翻譯

有兩個 Binary 的字串 `a` 和 `b`，需要回傳其加總後的 Binary 字串。

## 解法解析

這題如果只是當純的將字串轉換成數值，很容易遇到一個問題就是會超出數值資料格式的範圍。可能就會需要使用到 `BigInt` 或類似 `Long` 的資料格式。所以比較好的方式是針對各個 Bit 作處理。

### Bit-by-Bit Computation

這個解法很單純，就像是數值相加一樣，從個位數開始加，紀錄需要進位的值。

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

### Bit Manipulation

這解法主要使用了 Bitwise operator 來做處理。相加的話可以使用 `XOR` 來做處理，而是否需要進位的話則可以使用 `AND` 和 `Left shift` 來處理。但是這個解法就會需要 `Big Int` 或是 `Long` 的資料型態。所以如果程式語言沒有支援的話，就不適合使用此解法。

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

### 解法範例

#### Go

#### Bit-by-Bit Computation

```go
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

```go
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)
}
```

#### JavaScript

#### Bit-by-Bit Computation

```javascript
/**
 * @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

```javascript
/**
 * @param {string} a
 * @param {string} b
 * @return {string}
 */
var addBinary = function (a, b) {
    return (BigInt(`0b${a}`) + BigInt(`0b${b}`)).toString(2);
};
```

#### Kotlin

```kotlin
```

#### PHP

#### Bit-by-Bit Computation

```php
class Solution
{

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

            $answer[] = strval($carry % 2);
            $carry = floor($carry / 2);
        }

        if ($carry == 1) {
            $answer[] = '1';
        }
        $answer = array_reverse($answer);
        return implode('', $answer);
    }
}
```

##### Bit Manipulation

```php
```

#### Python

#### Bit-by-Bit Computation

```python
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
        answer = []
        for i in range(n - 1, -1, -1):
            if a[i] == '1':
                carry += 1
            if b[i] == '1':
                carry += 1

            answer.append(str(carry % 2))
            carry //= 2

        if carry == 1:
            answer.append('1')
        answer.reverse()
        return ''.join(answer)
```

##### Bit Manipulation

```python
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

```rust
```

#### Swift

```swift
```