#include <iostream>
#include <string>

using namespace std;

string AddBinary(string s1, string s2) 
{
    int len1 = s1.size()-1;
    int len2 = s2.size()-1;
    string s = len1 > len2? s1 : s2;
    int len = s.size()-1;
    char carry = '0';

    while(len1 >=0 && len2 >=0)
    {
        s[len] = (s1[len1] ^ s2[len2] ^ carry);
        carry = s1[len1] & s2[len2] | carry & s1[len1] |  carry & s2[len2];

        --len, --len1, --len2;
    }
	
	while(len1 >= 0)
	{
		s[len] = (s1[len1] ^ carry) + '0';
		carry = s1[len1] & carry;
		--len, --len1;
	}
	
	while(len2 >= 0)
	{
		s[len] = (s2[len2] ^ carry) + '0';
		carry = s2[len2] & carry;
		--len, --len2;
	}
	

    if (carry ^ '0') //if carry is '1', insert carry 
        s.insert(s.begin(), carry);

    return s;
}


int main(int argc, char** argv)
{
    string s = AddBinary("1", "111");
    cout << s << endl;
//
//	
//	s = AddBinary("11", "1");
//    cout << s << endl;
//	
//	s = AddBinary("101", "10");
//    cout << s << endl;
    return 0;
}