Title Description

Here are two binary strings , Returns the sum of them （ In binary ）.
Input is Non empty String and contains only numbers 1 and 0.

Input : a = “11”, b = “1”
Output : “100”

Example 2:

Input : a = “1010”, b = “1011”
Output : “10101”

Tips ：

 Each string consists only of characters  '0'  or  '1'  form .
1 <= a.length, b.length <= 10^4
 If the string is not  "0" , No leading zeros .

Their thinking

        The first way many people think of is to , Convert to binary decimal , And then add , Then convert the result into binary .
        This violent approach , In string a、b When the length is very small , Can achieve , But once the length exceeds the specified range , Data overflow will occur （ If the length is 10000,2 Of 10000 The power is far away long long int Representation range of ）. So this problem can't be solved in this way .
        The solution to this problem is the same as C++ The idea of adding large integers is the same as a hair , The idea of adding large integers . The only difference is that we deal with binary , Pay attention to the binary addition rules ( full 2 Into the 1).

Their thinking

Ideas , It's vertical calculation , Add item by item . Consider carrying , It's two in one , That is, if a bit is greater than or equal to 2, subtract 2 Is standard and , Then next ++, This is carry . Addition is at most into 1 position .

The code is as follows ：

string addBinary(string a, string b) {
    

	if(a.length()==1 and a[0]=='0')
		return b;
	if(b.length()==1 and b[0]=='0')
		return a;
		
	int i=a.length()-1;
	int j=b.length()-1;	
	string c;
   	int flag=0;// Used to determine whether there is carry  
    
    while(i >= 0 || j >= 0) 
	{
    
		if(i>=0 and j<0) // character string a Than b Long  
		{
    
			string x;
			x=a[i];
			if(flag==0)	// No carry  
			{
    
				c.insert(0,x);				
			}

			else	// Have carry  
			{
    
				if(int(a[i])==49) //49 yes '1' Of ASCII value  
				{
    
					c.insert(0,"0");
					flag=1;
				}
				else//'0' Corresponding 48 
				{
    
					c.insert(0,"1");
					flag=0;
				}
			}
			i--;
		}
		
		else if (j>=0 and i<0)// character string a Than b Long  
		{
    
			string x;
			x=b[j];
			if(flag==0)
			{
    
				c.insert(0,x);
			}
				
		
			else
			{
    
				if(int(b[j])==49) // The current position is '1' 49 yes '1' Of ASCII value  
				{
    
					c.insert(0,"0");
					flag=1;
				}
				else			// The current position is '0' 48 yes '0' Of ASCII value  
				{
    
					c.insert(0,"1");
					flag=0;
				}
			
			}
			j--;
		}
		
		else// character string a and b As long as  
		{
    
			if(flag==0)// No carry  
			{
    
				if(int(a[i])+int(b[j])==98)// The current position is '1' and '1' 49 yes '1' Of ASCII value  
				{
    
					c.insert(0,"0");
					flag=1;
				}	
				else if(int(a[i])+int(b[j])==96)// The current position is '0' and '0' 48 yes '0' Of ASCII value  
				{
    
					c.insert(0,"0");
					flag=0;
				}
				else		//0 and 1 1 and 0 
				{
    
					c.insert(0,"1");
					flag=0;
				}
				i--;
				j--; 
			}
			
			else// carry  
			{
    
				if(int(a[i])+int(b[j])==98)// The current position is '1' and '1' 49 yes '1' Of ASCII value  
				{
    
					c.insert(0,"1");
					flag=1;
				}	
				else if(int(a[i])+int(b[j])==96)// The current position is '0' and '0' 48 yes '0' Of ASCII value  
				{
    
					c.insert(0,"1");
					flag=0;
				}
				else		//0 and 1 1 and 0 
				{
    
					c.insert(0,"0");
					flag=1;
				}
				i--;
				j--; 
			}
		}
	}
    
    if(flag==1) // The highest bit has been carried , Need to move higher 1 
		c.insert(0,"1"); 
	
	return c;
    
}

// The test program 
#include<bits/stdc++.h>
using namespace std;
string addBinary(string a, string b)
{
    
// Copy the above 
}
int main()
{
    
	string a="1001";
	string b="111";
	cout<<addBinary(a,b);
}

         Maybe the code is long , There are still many improvements and optimizations . We are mainly to master and think about the idea of solving problems , The train of thought understands , You can A La . Understanding ideas 、 Understanding ideas ！！！！