0067. 二进制求和 Add Binary

问题描述

这个问题考察两个方面的知识:

• 逆序遍历字符串, 并从中解出每个字符. 这个很适合用迭代器
• 基本的加法操作, 要注意进位项 (carry), 每个比特位相加时, 都要加上进位项

下图展示的是 a = "1010"; b = "11011" 相加的过程:

代码写得就比较自然了, 就按上图描述的:

先构造出两个字符串的迭代器, 用于逆序遍历字符串, 这里为了方面, 我们直接用 a.as_bytes().iter().rev(), 它返回的类型是 Iter<Rev<u8>>.

#![allow(unused)]
fn main() {
use std::iter::Rev;
use std::slice::Iter;

pub fn add_binary1(a: String, b: String) -> String {
    let mut a_iter: Rev<Iter<u8>> = a.as_bytes().iter().rev();
    let mut b_iter = b.as_bytes().iter().rev();
    let mut result = Vec::with_capacity(a_iter.len().max(b_iter.len()) + 1);
    // 进位项
    let mut carry: u8 = 0;

    loop {
        let next_a = a_iter.next();
        let next_b = b_iter.next();
        // 循环的中止条件是, 所有字符串中的比特位都处理完, 且没有进位项.
        if carry == 0 && next_a.is_none() && next_b.is_none() {
            break;
        }

        // 计算当前比特位的值
        let mut bit = carry;
        if let Some(next_a) = next_a {
            bit += next_a - b'0';
        }
        if let Some(next_b) = next_b {
            bit += next_b - b'0';
        }
        // 更新进位项
        carry = bit / 2;
        bit %= 2;
        // 转换成 char 类型
        let bit_char = char::from(bit + b'0');
        result.push(bit_char);
    }

    // 逆序地将比特位转换成字符串
    result.iter().rev().collect()
}
}