首页 > 代码库 > Leetcode:Add Binary

Leetcode:Add Binary

戳我去解题

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

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

分析:高精度加法,只是将10进制的高精度加法 换成了 2进制的高精度加法

首先将 两个加数 反转一下,这样方便 从低位到高位顺序执行进位操作

这里我们有一个非常有用的技巧:

因为是加法操作,如果线性遍历过程中下标超出 加数字符串范围,那么我们将次加数的这个位置设为0

其实这个技巧在 链表加法中也有用到,非常利于统一管理 长度不一情况

class Solution {
public:
    string addBinary(string a, string b) {
          string res;
          int maxlen = max(a.size(), b.size());
          
          reverse(a.begin(), a.end());
          reverse(b.begin(), b.end());
          
          int carry = 0;
          for (int i = 0; i < maxlen; ++i) {
              int acur = (i < a.size() ? a.at(i) - 0 : 0);
              int bcur = (i < b.size() ? b.at(i) - 0 : 0);
              int val = (acur + bcur + carry) % 2;
              carry = (acur + bcur + carry) / 2;
              res.insert(res.begin(), val + 0);
          }
          if (carry == 1) {
              res.insert(res.begin(), 1);
          }
          return res;
    }
};