1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52 | class BinaryInteger {
private:
std::vector<bool> _bits;
public:
BinaryInteger() : _bits(1, false) {}
BinaryInteger(const std::string &s) {
int len = s.size();
_bits.resize(len);
for (int i = 0; i < len; i++)
_bits[i] = (s[len - i - 1] == '1');
}
string to_string() const {
std::string s;
s.reserve(_bits.size());
for (int i = _bits.size() - 1; i >= 0; i--)
if (_bits[i])
s += '1';
else
s += '0';
return s;
}
friend BinaryInteger operator+(const BinaryInteger &a,
const BinaryInteger &b) {
BinaryInteger out;
out._bits.clear();
int carry = 0;
int len = std::max(a._bits.size(), b._bits.size());
for (int i = 0; i < len || carry != 0; i++) {
int sum = carry;
if (i < a._bits.size())
sum += a._bits[i];
if (i < b._bits.size())
sum += b._bits[i];
out._bits.push_back(sum % 2);
carry = sum / 2;
}
return out;
}
};
class Solution {
public:
string addBinary(string strA, string strB) {
BinaryInteger A(strA);
BinaryInteger B(strB);
BinaryInteger C = A + B;
return C.to_string();
}
};
|