二级制求和

public class Solution {
    public String addBinary(String a, String b) {
        if(a == null || a.length() == 0)
        	return b;
        if(b == null || b.length() == 0)
        	return a;
        
        // 首先让a，b变得一样长
        while(a.length() > b.length())
        	b = "0" + b;
        while(a.length() < b.length())
        	a = "0" + a;
        
        String res = "";
        boolean carryFlag = false;
        for(int i = a.length() - 1; i >= 0; i--){
        	if(a.charAt(i) - '0' + b.charAt(i) - '0' == 1)
        		res = carryFlag ? "0" + res : "1" + res;
        	else if(a.charAt(i) - '0' + b.charAt(i) - '0' == 2){ // 存在进位
        		res = carryFlag ? "1" + res : "0" + res;
        		carryFlag = true;
        	}
        	else { // 0
        		res = carryFlag ? "1" + res : "0" + res;
        		carryFlag = false;
			}
        }
        
        if(carryFlag)
        	res = "1" + res;
        
        return res;
    }
}

思路很简单，先把短的字符串补齐，然后逐位相加。
string addBinary(string a, string b)
{
    int length = max(a.size(), b.size());
    string res(length + 1, ' ');
    char flag = '0';
    while (length > a.size())
    {
        a = "0" + a;
    }
    while (length > b.size())
    {
        b = "0" + b;
    }
    for (int i = length - 1; i >= 0; --i)
    {
        int ch = a[i] + b[i] + flag - 3 * '0';
        if (ch == 3)
        {
            res[i + 1] = '1'; flag = '1';
        }
        else if (ch == 2)
        {
            res[i + 1] = '0'; flag = '1';
        }
        else
        {
            res[i + 1] = ch + '0';
            flag = '0';
        }    
    }
    if (flag == '1') res[0] = '1';
    else res = res.substr(1);
    return res;
}

/*
	 * 用StringBuilder比用String和StringBuffer速度更快
	 */
	public String addBinary(String a, String b) {
		StringBuilder res = new StringBuilder();
		int i = a.length() - 1, j = b.length() - 1, carry = 0;

		while (i >= 0 || j >= 0 || carry != 0) {
			int sum = carry;
			if (i >= 0)
				sum += a.charAt(i--) - '0';
			if (j >= 0)
				sum += b.charAt(j--) - '0';
			res.append(sum % 2);
			carry = sum / 2;
		}
		//res是倒序，必须进行反转
		return res.reverse().toString();
	}

class Solution {
public:
    string addBinary(string a, string b) {
        int l1=a.length()-1,l2=b.length()-1;
        string sum = "";
        int s=0,c=0;
        while(l1>=0 || l2>=0 || c)
        {
        	int num1 = l1>=0?a[l1--]-'0':0;
        	int num2 = l2>=0?b[l2--]-'0':0;
        	s = num1 + num2 + c;
        	c = s>>1;
        	sum = char(s%2 + '0') + sum;
		}
		return sum;
    }
};

//.对string进行翻转：reverse(str.begin().str.end());
class Solution {
public:
    string addBinary(string a, string b) {
           reverse(a.begin(),a.end());
           reverse(b.begin(),b.end());
           string ans;
           int i,cnt=0;
           for(i=0;i<a.size()||i<b.size();i++){
               if(i<a.size()&&a[i]=='1') cnt++;
               if(i<b.size()&&b[i]=='1') cnt++;
               if(cnt&1){
                  ans+='1';
                  if(cnt==3) cnt=1;
                  else cnt=0; //记得清零
               }else{
                  ans+='0';
                  if(cnt==2) cnt=1;
                  else cnt=0;
               }
           }
           if(cnt) ans+='1';
           reverse(ans.begin(),ans.end());
           return ans;
    }
};

class Solution {
public:
 string addBinary(string a, string b) 
  {
    int aLen=a.length()-1,bLen=b.length()-1;
   string res = "";
   int sum=0,carry=0;
   while(aLen>=0 || bLen>=0 || carry)
   {
       int sum1=aLen>=0?a[aLen--]-'0' : 0;
       int sum2=bLen>=0?b[bLen--]-'0' : 0;
       sum = carry+sum1+sum2;
       carry = sum/2;
       res = char('0'+sum%2)+res;
   }
   return res;
  }
};

import java.util.*;


public class Solution {
    /**
     * 
     * @param a string字符串 
     * @param b string字符串 
     * @return string字符串
     */
    public String addBinary (String a, String b) {
        //判空
        if(a==""||a.length()==0){
            return b;
        }
        if(b==""||b.length()==0){
            return a;
        }
        //补齐长度
        while(a.length()>b.length()){
            b="0"+b;
        }
        while(a.length()<b.length()){
            a="0"+a;
        }
        String res="";
        boolean carry=false;
        for(int i=a.length()-1;i>=0;i--){
            if(a.charAt(i)-'0'+b.charAt(i)-'0'==1){
                //1 0 1和0本身相加没有进位，但是受到外界进位的影响，
                //因此，其进位设置为一不确定值，若无进位，直接输出一系列1，
                //若有进位，在for循环外通过if条件判断加1
                res=carry?"0"+res:"1"+res;
            }else if(a.charAt(i)-'0'+b.charAt(i)-'0'==2){
                //1 1 两个1本身相加是有进位的，不论外界是否有进位，
                //其进位设置都应该为true
                res=carry?"1"+res:"0"+res;
                carry=true;
            }else{//0 0 两个零本身相加是没有进位的，不论外界是否有进位，
                //其进位设置都应该为false
                res=carry?"1"+res:"0"+res;
                carry=false;
            }
        }
        if(carry){
            res="1"+res;
        }
        return res;
    }
}

    /*
    * 目的：两个字符串相加，与字符串+1的那一道差不多
    * 方法：先把短的字符串补齐，然后逐位相加
    */
    string addBinary(string a, string b) {
        int carry = 0;
         int len = max(a.size(),b.size());
        string res(len+1, ' ');
        while(len>a.size()){
            a="0"+a;
        }
        while(len>b.size()){
            b="0"+b;
        }
        for (int i = a.size()-1; i>=0;--i){
            int a1 = a[i]-'0';
            int a2 = b[i]-'0';
            res[i+1]= '0'+(a1+a2+carry)%2;
            carry = (a1+a2+carry)/2;
        }
        if (carry>0)
            res[0] = '1';
        else
            res=res.substr(1,len);
        return res;
    }

//思路：很容易想到，从最后一位开始算起，维护一个carry进位符，遍历两个字符串，
//result每次计算两个对应位之和加上进位符的值，对之和进行比较,最后需要注意，如果
//遍历完之后进位符依然为1，则在结果之前加1即可
class Solution {
public:
    string addBinary(string a, string b) {
        int len1 = a.length();
        int len2 = b.length();
        int carry = 0;
        std::string res;
        int i = len1 - 1, j = len2 - 1;
        while (i >= 0 && j >= 0)
        {
            int result = a[i] + b[j] + carry - 96;    
            add(result, res, carry);
            --i; --j;
        }
        while (i >= 0)
        {
            int result = a[i] - 48 + carry;
            add(result, res, carry);
            --i;
        }
        while (j >= 0)
        {
            int result = b[j] - 48 + carry;
            add(result, res, carry);
            --j;
        }
        if (carry > 0)
            res = to_string(1) + res;
        return res;

    }

private:
    void add(int result, string& res,int& carry)
    {
        if (result >= 2)
        {
            carry = 1;
            result = result-2;
        }
        else if (result < 2)
            carry = 0;
        res = to_string(result) + res;
    }
};

string addBinary(string a, string b) {
    if (a.length() == 0 || b.length() == 0)
        return "";
    int n = a.length();
    int m = b.length();
    int j = m - 1, i = n - 1;
    string res;
    int flag = 0;
    for (; j >= 0 || i >= 0; --j, --i) {    //分析每一位的情况
        if (j >= 0 && i >= 0) {    //在该位置都存在字符
            if (a[i] == '1' && b[j] == '1') {    //都为1
                if (!flag) {    //前一位不存在进位
                    res.push_back('0');

                }
                else {     //前一位存在进位           
                        res.push_back('1');
                }
                flag = 1;    //该位一定产生进位
            }
            else if ((a[i] == '1' && b[j] == '0') || (a[i] == '0' && b[j] == '1')) {
                //一个为0，一个为1
                if (!flag) {    // 前一位不存在进位                 
                   res.push_back('1');
                    flag = 0;    //该位不产生进位
                }
                else {    //前一位存在进位
                    res.push_back('0');
                    flag = 1;    //该位产生进位
                }

            }
            else if (a[i] == '0' && b[j] == '0') {    //都为0
                if (!flag) {    //前一位不存在进位
                    res.push_back('0');

                }
                else {    //前一位存在进位
                    res.push_back('1');
                }
                flag = 0;    //该位一定不存在进位
            }
        }
        else if (j >= 0) {    //b的长度大于a,分析b剩余未相加的部分
            if (b[j] == '1') {    //该位为1时
                if (!flag) {    //前一位不存在进位
                    res.push_back('1');
                    flag = 0;    //该位不产生进位
                }
                else {    //前一位存在进位
                    res.push_back('0');
                    flag = 1;    //该位产生进位
                }
            }
            else if (b[j] == '0') {    //该位为0时
                if (!flag) {    //前一位不存在进位
                    res.push_back('0');

                }
                else {    //前一位存在进位
                    res.push_back('1');

                }
                flag = 0;    //该位一定不产生进位
            }

        }
        else if (i >= 0) {    //a的长度大于b，分析a剩余未相加的部分，下面分析与上面类似
            if (a[i] == '1') {
                if (!flag) {
                    res.push_back('1');
                    flag = 0;
                }
                else {
                    res.push_back('0');
                    flag = 1;
                }
            }
            else if (a[i] == '0') {
                if (!flag) {
                    res.push_back('0');

                }
                else {
                    res.push_back('1');

                }
                flag = 0;
            }
        }
    }
    if (flag)    //最后一位产生了进位
        res.push_back('1');
    reverse(res.begin(), res.end());    //反转整个字符串
    return res;
}

public class Solution {
    public static String addBinary(String a, String b) {
		while (a.length() > b.length()) 
			b = "0" + b;
		while (a.length() < b.length()) 
			a = "0" + a;
		String res = "";
		boolean jinwei = false;
		for (int i = a.length() - 1; i >= 0; i -- ) {
			if(a.charAt(i) - '0' + b.charAt(i) - '0' == 1) {
				res = jinwei ? "0" + res : "1" + res;
			} else if(a.charAt(i) - '0' + b.charAt(i) - '0' == 2) {
				res = jinwei ? "1" + res : "0" + res;
				jinwei = true;
			} else {
				res = jinwei ? "1" + res : "0" + res;
				jinwei = false;
			}
		}
		if(jinwei) res = "1" + res;
		return res;
	}
}

class Solution {
public:
    string addBinary(string a, string b) {
        int i,j,c=0,N=a.length(),M=b.length();
        string d="";
        for(i=N-1,j=M-1;i>=0||j>=0;i--,j--)
        {
            int t1,t2,t3;
            char t;
            if(i>=0&&j<0){ t1=a[i]-'0'; t2=0; }
            if(i<0&&j>=0){ t1=0; t2=b[j]-'0'; }
            if(i>=0&&j>=0){ t1=a[i]-'0'; t2=b[j]-'0'; }
            t3=t1+t2+c;
            if(t3>=2){ t3-=2; c=1; }
            else c=0;
            t=t3+'0';
            d=t+d;
        }
        if(c==1) d='1'+d;
        return d;
    }
};

public class Solution {
    public String addBinary(String a, String b) {
        if(a==null)
    		return b;
    	if(b==null)
    		return a;
    	char[] longchar,shortchar;
    	int sub = 0;
    	if(a.length()>=b.length()){
    		sub = a.length()-b.length();
    		longchar = a.toCharArray();
    		shortchar = b.toCharArray();
    	}else{
    		sub = b.length()-a.length();
    		longchar = b.toCharArray();
    		shortchar = a.toCharArray();
    	}
    	char f = 0;//进位
    	char[] result = new char[longchar.length+1];
    	int j = result.length-1;
    	char r;//结果
    	for(int i = longchar.length-1;i>=0;i--){
    		char lc = longchar[i];
    		char sc = i-sub>=0?shortchar[i-sub]:'0';
    		if(lc==sc){
    			if(lc=='1'){
					r = f == '1' ? '1' : '0';
    				f = '1';
    			}else{
					r = f == '1' ? '1' : '0';
    				f = '0';
    			}
    		}else{
				r = f == '1' ? '0' : '1';
				f = f == '1' ? '1' : '0';
    		}
    		result[j--] = r;
    	}
    	if(f=='1'){
    		result[j] = f;
    	}else{
    		j++;
    	}
        return new String(result, j, result.length-j);
    }
}

    string addBinary(string a, string b) {
        string sum;
        int lena = a.length(), lenb = b.length(), jinwei = 0, temp;
        while(lena > 0 || lenb > 0){
            temp = (lena > 0 && lenb >0 ) ? 
                    (a[lena-1] - '0' + b[lenb-1] - '0' + jinwei):
                    ((lena > 0 ) ? (a[lena-1] - '0' + jinwei):
                    (b[lenb - 1] - '0' + jinwei));
            if(temp > 1){
                jinwei = 1; sum.push_back(temp -2 + '0');
            }else{
                jinwei = 0; sum.push_back(temp + '0');
            } 
            --lena; --lenb;
        }
        if(jinwei) sum.push_back('1');
        reverse(sum.begin(), sum.end());
        return sum;
    }

class Solution {
public:
    /**
     * 
     * @param a string字符串 
     * @param b string字符串 
     * @return string字符串
     */
    string addBinary(string a, string b) {
        // write code here
        string res = "";
        stack<int> s;
        int m = a.size() - 1, n = b.size() - 1, carry = 0; 
        int min = m > n ? n : m;
        while(min-- >= 0)
        {
            int temp = (a[m--] - '0') + (b[n--] - '0') + carry;
            if(temp >= 2)
            {
                s.push(temp - 2);
                carry = 1;
            }
            else
            {
                s.push(temp);
                carry = 0;
            }
        }
        while(m >= 0)
        {
            int temp = (a[m--] - '0') + carry;
            if(temp >= 2)
            {
                s.push(temp - 2);
                carry = 1;
            }
            else
            {
                s.push(temp);
                carry = 0;
            }
        }
        while(n >= 0)
        {
            int temp = (b[n--] - '0') + carry;
            if(temp >= 2)
            {
                s.push(temp - 2);
                carry = 1;
            }
            else
            {
                s.push(temp);
                carry = 0;
            }
        }
        if(carry)
            s.push(carry);
        while(!s.empty())
        {
            res += (s.top() + '0');
            s.pop();
        }
        return res;
    }
};

简单的二进制进位，用两个指针分别指向两个字符串，从后向前遍历：

1. 如果有进位，保存进位，然后将剩余部分加入新字符串
2. 遍历完某个字符串后，如果存在进位或另一个字符串没有遍历完，继续处理剩余部分
3. 遍历完毕后将字符串进行反转即可

代码如下：

//
// Created by jt on 2020/9/26.
//
#include <string>
using namespace std;

class Solution {
public:
    /**
     *
     * @param a string字符串
     * @param b string字符串
     * @return string字符串
     */
    string addBinary(string a, string b) {
        // write code here
        string c;
        int p = a.size() - 1, q = b.size() - 1, carry = 0;
        while (p >= 0 && q >= 0) {
            int d =  a[p] - '0' + b[q] - '0' + carry;
            if (d > 1) { carry = 1; c.push_back(d - 2 + '0'); }
            else { carry = 0; c.push_back(d+'0'); }
            --p; --q;
        }
        while (p >= 0) {
            int d = a[p] - '0' + carry;
            if (d > 1) { carry = 1; c.push_back(d - 2 + '0'); }
            else { carry = 0; c.push_back(d+'0'); }
            --p;
        }
        while (q >= 0) {
            int d = b[q] - '0' + carry;
            if (d > 1) { carry = 1; c.push_back(d - 2 + '0'); }
            else { carry = 0; c.push_back(d+'0'); }
            --q;
        }
        if (carry == 1) c.push_back('1');
        reverse(c.begin(), c.end());
        return c;
    }
};