二进制求和

1 题目复现

1）描述

给定两个二进制字符串，返回他们的和（用二进制表示）。

2）样例

a = 11
b = 1
返回 100

2 简单实现（C++）

<code>
class Solution
{
public:
/**
* @param a a number
* @param b a number
* @return the result
*/
string addBinary(string& a, string& b)
{
string result = "";
int c = 0, num = 0;
int i = a.size() - 1, j = b.size() - 1;
for (; i >= 0 && j >= 0; i--, j--)
{
num = (a[i] - '0') + (b[j] - '0') + c;
c = num / 2;
num = num % 2;
result += ('0' + num);
}
for (; i >= 0; i--)
{
num = (a[i] - '0') + c;
c = num / 2;
num = num % 2;
result += ('0' + num);
}
for (; j >= 0; j--)
{
num = (b[j] - '0') + c;
c = num / 2;
num = num % 2;
result += ('0' + num);
}
if (c != 0)
{
result += ('0' + c);
}
i = 0; j = result.size() - 1;
while (i < j)
{
char temp = result[i];
result[i] = result[j];
result[j] = temp;
i++; j--;
}
return result;
}
</code>

3 进阶实现（JAVA）

1）目标

不使用“+”实现

2）实现代码

<code>
public class Solution {

public String addBinary(String a, String b) {
    // Write your code here
    if(a.equals("0") && b.equals("0")) return a;
    if(checkZero(a)) return delZeroes(b);
    if(checkZero(b)) return delZeroes(a);
    int asize = a.length();
    int bsize = b.length();
    int len = 0;
    if( asize > bsize) {
        b = addZeroes(b, asize-bsize);
        len = asize;
    } else {
        a = addZeroes(a, bsize-asize);
        len = bsize;
    } 
    String na = addBinaryXOR(a, b, len);
    String nb = addBinaryAND(a, b, len) + "0";
    return addBinary(na, nb);
}
private boolean checkZero(String c) {
    for(int i=0; i<c.length(); i++) {
        if(c.charAt(i)!='0')
        return false;
    }
    return true;
}
private String delZeroes(String d) {
    int len = d.length();
    int count = 0;
    while(d.charAt(count)=='0') {
        count++;
    }
    return d.substring(count, len);
}
private String addZeroes(String t, int n) {
    StringBuilder builder = new StringBuilder();
    while(n > 0) {
        builder.append('0');
        n--;
    }
    builder.append(t);
    return builder.toString();
}
private String addBinaryAND(String a, String b, int len) {
    StringBuilder builder = new StringBuilder();
    for(int i=0; i<len; i++) {
        if(a.charAt(i)=='1' && b.charAt(i)=='1')
        builder.append("1");
        else 
        builder.append( "0");
    }
    return builder.toString();
}
private String addBinaryXOR(String a, String b, int len) {
    StringBuilder builder = new StringBuilder();
    for(int i=0; i<len; i++) {
        if(a.charAt(i)==b.charAt(i))
        builder.append("0");
        else 
        builder.append("1");
    }
    return builder.toString();
}

}
</code>