/*
Given two binary strings, return their sum (also a binary string).

For example,
a = "11"
b = "1"
Return "100".

*/
/*
Thinking:
由于是计算和，那么最多的长度也只是 a, b 最大长度 +1
先把a, b 转换为整形，然后通过余数和商来计算进位,
根据计算结果和进位，来判断放入到字符串数组里面的值。
//Error1: 如果转换为整型，则很容易出现数值过大越界的情况
*/

func addBinary(_ a: String, _ b: String) -> String {
    guard a.lengthOfBytes(using: .ascii) > 0, b.lengthOfBytes(using: .ascii) > 0 else {
        return ""
    }
    /*
        根据位数计算进位与和
    */
    func calc(_ lhs: Character, _ rhs: Character, _ carry: Bool) -> (String, Bool) {
        switch (lhs, rhs, carry) {
        case ("1", "1", false), ("0", "1", true), ("1", "0", true):
            return ("0", true)
        case ("1", "1", true):
            return ("1", true)
        case ("0", "1", false), ("1", "0", false), ("0", "0", true):
            return ("1", false)
        case ("0", "0", false):
            return ("0", false)
        default:
            return ("0", false)
        }
    }

    //如果为负数了，直接拿到的是0
    func character(at index: Int, _ charactersArray: String) -> Character {
        guard index >= 0, index < charactersArray.characters.count else {
            return "0"
        }
        return charactersArray.characters[charactersArray.index(charactersArray.startIndex, offsetBy: index)]
    }

    let aLength = a.lengthOfBytes(using: .ascii)
    let bLength = b.lengthOfBytes(using: .ascii)
    var lIndex = aLength - 1, rIndex = bLength - 1
    var lRemainder: Character = "0", rRmainder: Character = "0"    //余数
    var carry = false //是否产生进位
    let maxLength = max(aLength, bLength) + 1
    var charactersArray = Array<Character>(repeating: "0", count: maxLength)
    var step = maxLength - 1

    while step != 0 {
        let result: String
        lRemainder = character(at: lIndex, a)
        rRmainder = character(at: rIndex, b)
        (result, carry) = calc(lRemainder, rRmainder, carry)
        charactersArray[step] = Character(String(result))
        lIndex -= 1
        rIndex -= 1
        step -= 1
    }

    if carry, step >= 0 {
        charactersArray[step] = "1"
    }

    print(charactersArray)
    //去掉前面多余的零
    var dropIndex = 0
    for (index, value) in charactersArray.enumerated() {
        dropIndex = index
        if value == "1" {
            break
        }
    }
    print(dropIndex)
    charactersArray = Array<Character>(charactersArray.dropFirst(dropIndex))
    print(charactersArray)
    return String(charactersArray)

}

print(addBinary("10100000100100110110010000010101111011011001101110111111111101000000101111001110001111100001101",
        "110101001011101110001111100110001010100001101011101010000011011011001011101111001100000011011110011"))