string Solution::addBinary(string A, string B) {
reverse(A.begin(),A.end());
reverse(B.begin(),B.end());
if(A.size()<B.size()) {
while(A.size()!=B.size()) A.push_back('0');
}
else while(A.size()!=B.size()) B.push_back('0');
int m=A.size();
if(m==0) return B;
string res;
int carry=0,i=0;
while(i<m || carry)
{
int val=0;
if(i<m) val=A[i]-'0'+B[i]-'0';
val+=carry;
carry=val/2;
res.push_back(val%2+'0');
i++;
}
while(res.size()>1 && res[res.size()-1]=='0') res.pop_back();
reverse(res.begin(),res.end());
return res;
}