Giả sử chúng ta có hai chuỗi nhị phân a và b, chúng ta phải cộng các số nhị phân này và tìm tổng của chúng, cũng như một chuỗi.
Vì vậy, nếu đầu vào là a ="10110", b ="10010", thì đầu ra sẽ là "101000".
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- ret:=chuỗi trống
- na:=kích thước của a, nb:=kích thước của b
- i:=na - 1, j:=nb - 1
- mang:=0
- while (i> =0 hoặc j> =0), do:
- addA:=(nếu i> =0 thì a [i] - ASCII của '0', nếu không thì 0)
- addB:=(nếu j> =0, thì b [j] - ASCII của '0', nếu không thì 0)
- sum:=addA + addB + carry
- carry:=sum / 2
- sum:=sum mod 2
- ret:=ret nối tổng
- (giảm i đi 1)
- (giảm j đi 1)
- nếu carry là khác 0, thì:
- ret:=ret nối mang
- đảo ngược mảng ret
- trả lời lại
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
#include <bits/stdc++.h>
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;
}
};
main(){
string a = "10110", b = "10010"; Solution ob;
cout << ob.solve(a, b);
} Đầu vào
"10110","10010"
Đầu ra
101000