剑指leetcode—二进制求和

题目描述： 给你两个二进制字符串，返回它们的和（用二进制表示）。

输入为 非空 字符串且只包含数字 1 和 0。

示例 1:

输入: a = “11”, b = “1” 输出: “100”

示例 2:

输入: a = “1010”, b = “1011” 输出: “10101”

提示：

每个字符串仅由字符 '0' 或 '1' 组成。
1 <= a.length, b.length <= 10^4
字符串如果不是 "0" ，就都不含前导零。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-binary
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

方法一

使用函数库求和

将a和b都转化为十进制数

• 求和
• 将求和结果转化为二进制数

java实现

class Solution{
	public String addBinary(String a,String b){
		int res=Integer.parseInt(a,2)+Integer.parseInt(b,2));
		return Integer.toBinaryString(res);
		}
}

但是该方法，受输入字符串a和b的长度限制，字符串太大时，不可以将其转换为Integer，Long，BigIngeter类型。
如果输入的数字很大，效率很低

方法二：

逐位计算

原理类似与字符串相加
只不过字符串相加，是满十进一位，此处是满二进一位

class Solution {
  public String addBinary(String a, String b) {
    int n=a.length()-1;
    int m=b.length()-1;
    int carry=0;
    StringBuilder res=new StringBuilder();
    while(n>=0||m>=0)
    {
        int p=n<0? 0:a.charAt(n)-'0';
        int q=m<0? 0:b.charAt(m)-'0';
        //余数作为二进制的数
        int temp=(p+q+carry)%2;
        res.append(temp);
        //下一次计算的进位
        carry=(p+q+carry)/2;
        n--;
        m--;
    }
    //最后判断最高位是否为1.为1则加入结果
    res.append(carry==1? carry:"");
    return res.reverse().toString();//先翻转后化为字符串
  }
}

方法三：

位操作

待更新

参考官方题解