题目介绍

复杂度

时间复杂度: O(Max(m, n)), 空间复杂度: O(Max(m, n))

解题思路

函数

使用内置函数，但是打印了下最大支持，理论上是超过 64 位 1 就不行了。

转成十进制
相加
转成二进制输出

func addBinary(_ a: String, _ b: String) -> String {
    let max = String(UInt64.max)
    print("\(max) has \(max.count) digits.")
    return String((UInt64(a, radix: 2) ?? 0) + (UInt64(b, radix: 2) ?? 0), radix: 2)
}

位运算

首先说明和上面问题一样，Int 64 的局限性，说下思路。

看到二进制的题目，要善用位运算。
相加用位运算分两步：

按位异或 ^ ：算出不进位每一位的相加值
按位与 & 并左移以为 << ：算出需要进位的二进制值

func addBinary(_ a: String, _ b: String) -> String {
        var x = Int(a, radix: 2) ?? 0
        var y = Int(b, radix: 2) ?? 0
        var ans: Int = 0
        var carry: Int = 0
        while y != 0 {
            ans = x ^ y
            carry = (x & y) << 1
            x = ans
            y = carry
        }
        return String(ans, radix: 2)
    }

String

class Solution {
    func addBinary(_ a: String, _ b: String) -> String {
        let a = Array(a)
        let b = Array(b)
        var ans = ""
        var carry = 0
        var i = a.count - 1
        var j = b.count - 1
        while i >= 0 || j >= 0 || carry > 0 {
            if i >= 0 {
                carry += Int(String(a[i]))!
                i -= 1
            }
            if j >= 0 {
                carry += Int(String(b[j]))!
                j -= 1
            }
            ans = "\(carry % 2)" + ans
            carry = carry / 2
        }
        return ans
    }
    /**
    func addBinary(_ a: String, _ b: String) -> String {
        let max = String(UInt64.max)
        print("\(max) has \(max.count) digits.")
        return String((UInt64(a, radix: 2) ?? 0) + (UInt64(b, radix: 2) ?? 0), radix: 2)
    }
    func addBinary(_ a: String, _ b: String) -> String {
        var x = Int(a, radix: 2) ?? 0
        var y = Int(b, radix: 2) ?? 0
        var ans: Int = 0
        var carry: Int = 0
        while y != 0 {
            ans = x ^ y
            carry = (x & y) << 1
            x = ans
            y = carry
        }
        return String(ans, radix: 2)
    }
    */
}

/**
看到二进制的题目，要善用位运算。
相加用位运算分两步：
- 按位异或 ^ ：算出不进位每一位的相加值
- 按位与 & 并左移以为 << ：算出需要进位的二进制值
*/

**版权声明**

Ivan’s Blog by Ivan Ye is licensed under a Creative Commons BY-NC-ND 4.0 International License.
由叶帆创作并维护的叶帆的博客博客采用创作共用保留署名-非商业-禁止演绎4.0国际许可证。

本文首发于Ivan’s Blog | 叶帆的博客博客（ http://yeziahehe.com ），版权所有，侵权必究。

本文链接：http://yeziahehe.com/2020/03/07/AddBinary/