Chương trình cộng hai chuỗi nhị phân, trả về chuỗi nhị phân trong C++

Cho hai chuỗi nhị phân a và b, thực hiện phép cộng nhị phân và trả về kết quả cũng dưới dạng chuỗi.

Ví dụ, a = "10110", b = "10010", đầu ra là "101000".

Các bước giải quyết:

• ret := chuỗi rỗng.
• na := độ dài a, nb := độ dài b.
• i := na - 1, j := nb - 1.
• carry := 0.
• Trong khi i >= 0 hoặc j >= 0:
  • addA := (i >= 0) ? a[i] - '0' : 0.
  • addB := (j >= 0) ? b[j] - '0' : 0.
  • sum := addA + addB + carry.
  • carry := sum / 2.
  • sum %= 2.
  • ret += to_string(sum).
  • Giảm i và j.
• Nếu carry != 0, thêm carry vào ret.
• Đảo ngược ret.
• Trả về ret.

Ví dụ minh họa

#include 
using namespace std;

class Solution {
public:
    string solve(string a, string b) {
        string ret = "";
        int na = a.size();
        int nb = b.size();
        int i = na - 1;
        int j = nb - 1;
        int carry = 0;
        while (i >= 0 || j >= 0) {
            int addA = i >= 0 ? a[i] - '0' : 0;
            int addB = j >= 0 ? b[j] - '0' : 0;
            int sum = addA + addB + carry;
            carry = sum / 2;
            sum %= 2;
            ret += to_string(sum);
            i--;
            j--;
        }
        if (carry)
            ret += to_string(carry);
        reverse(ret.begin(), ret.end());
        return ret;
    }
};

int main() {
    string a = "10110", b = "10010";
    Solution ob;
    cout << ob.solve(a, b);
}

Đầu vào

"10110","10010"

Đầu ra

101000