Any more efficient method for Add Binary?

Question

The following is my solution for this problem. Actually, it takes me much time to get through this perfectly. I want to know are there any other better solution for this problem? If anyone has a better and more efficient and less complicated method, please share with us.

public static String addBinary(String a, String b) {
    long sum = 0;
    String resultString = "";
    List<String> aStrings = new LinkedList<String>();
    List<String> bStrings = new LinkedList<String>();
    int len_a = a.length();
    int i = len_a;
    int carry = 0;
    while (i - 16 > 0) {
        aStrings.add(a.substring(i - 16, i));
        i = i - 16;
    }
    aStrings.add(a.substring(0, i));

    int len_b = b.length();
    i = len_b;
    while (i - 16 > 0) {
        bStrings.add(b.substring(i - 16, i));
        i = i - 16;
    }
    bStrings.add(b.substring(0, i));
    int index = 0;

    while (index < Math.min(aStrings.size(), bStrings.size())) {
        long binary_a = stringToInteger(aStrings.get(index));
        long binary_b = stringToInteger(bStrings.get(index));
        sum = binary_a + binary_b + carry;
        String tempString = binaryToString(sum);
        if (tempString.length() > 16) {
            carry = 1;
            tempString = tempString.substring(1);
            resultString = tempString + resultString;
        } else {
            carry = 0;
            if (index < Math.max(bStrings.size()-1,aStrings.size()-1)) {
                while (tempString.length() < 16) {
                    tempString = "0" + tempString;
                }
            }
            resultString = tempString + resultString;
        }
        index++;
    }
           //add the rest of a string
    while (index < aStrings.size()) {
        long binary_a = stringToInteger(aStrings.get(index));
        long binary_b = 0;
        sum = binary_a + binary_b + carry;
        String tempString = binaryToString(sum);
        if (tempString.length() > 16) {
            carry = 1;
            tempString = tempString.substring(1);
            resultString = tempString + resultString;
        } else {
            carry = 0;
            if (index != aStrings.size()-1 ) {
                while (tempString.length() < 16) {
                    tempString = "0" + tempString;
                }
            }
            resultString = tempString + resultString;
        }
        index++;
    }
            // add the rest of b string
    while (index < bStrings.size()) {
        long binary_a = 0;
        long binary_b = stringToInteger(bStrings.get(index));
        sum = binary_a + binary_b + carry;
        String tempString = binaryToString(sum);
        if (tempString.length() > 16) {
            carry = 1;
            tempString = tempString.substring(1);
            resultString = tempString + resultString;
        } else {
            carry = 0;
            if (index != bStrings.size()-1) {
                while (tempString.length() < 16) {
                    tempString = "0" + tempString;
                }
            }
            resultString = tempString + resultString;
        }
        index++;
    }
    //add the last carry
    if(carry==1){
        resultString="1"+resultString;
    }

    return resultString;
}

public static long stringToInteger(String s) {
    if (s == "") {
        return 0;
    }
    int result = 0;
    int len = s.length();
    if (s.equals("0")) {
        return 0;
    }
    for (int i = 0; i < len; i++) {
        if (s.charAt(len - 1 - i) == '1') {
            result += Math.pow(2, i);

        }
    }
    return result;
}

public static String binaryToString(long num) {
    String result = "";
    long temp = num;
    int maxPow = 0;
    int sum = 0;
    while (Math.pow(2, maxPow) <= temp) {
        maxPow++;
    }
    if (maxPow != 0) {
        maxPow--;
    }
    for (int pow = maxPow; pow >= 0; pow--) {

        if ((sum + Math.pow(2, pow)) <= temp) {
            sum += Math.pow(2, pow);
            result = result + "1";
        } else {
            result = result + "0";
        }
    }
    return result;
}

Answer 1

No need extract space with linklist the c code show as

string addBinary(string a, string b) {
int aLength = a.size();
int bLength = b.size();
size_t maxLength = max(aLength, bLength);
string result;
result.reserve(maxLength + 1);
int carrier = 0;
char ch;
int xst;
while (aLength && bLength) {
    xst = carrier + a[--aLength]
    + b[--bLength] - 0x60;
    carrier = xst>>1;
    ch = (xst&0x1) + 0x30;
    result.push_back(ch);
}
while (aLength > 0) {
    xst = carrier + a[--aLength] - 0x30;
    carrier = xst>>1;
    ch = (xst&0x1) + 0x30;
    result.push_back(ch);
}
while (bLength > 0) {
    xst = carrier + b[--bLength] - 0x30;
    carrier = xst>>1;
    ch = (xst&0x1) + 0x30;
    result.push_back(ch);
}
if (carrier) {
    result.push_back('1');
}
reverse(result.begin(), result.end());
return result;
}

Answer 2

here's JAVA solution, without using linked list. The idea is simple and straightforward. when adding two binary digits, if both are 1 memorize 1 and drop down 0. if memorized element is 1, and both elements are 1, drop down 1, memorize one. Otherwise drop down the number and memorized elements is 0. ctoi is additional function to convert char into int.

public class Solution 
{
    int ctoi(char c)
    {
        switch(c)
        {
            case '0': return 0;
            case '1': return 1;
            default: return -1;
        }
    }
    String add(String s1, String s2)
    {
        StringBuffer sb1 = new StringBuffer(s1);
        StringBuffer sb2 = new StringBuffer(s2);
        StringBuffer sb3 = new StringBuffer();
        while (sb1.length() != sb2.length())
        {
            if (sb1.length()<sb2.length())
                sb1.insert(0,"0");
            else
                sb2.insert(0,"0");
        }
        int r=0, size = sb1.length();
        char c;
        for (int i=size-1; i>=0; i--)
        {
            int sum = ctoi(sb1.charAt(i)) + ctoi(sb2.charAt(i)) + r;
            if (sum == 3) {c = '1'; r = 1;}
            else if (sum == 2) {c = '0'; r = 1;}
            else if (sum == 1) {c = '1'; r = 0;}
            else if (sum == 0) {c = '0'; r = 0;}
            else { c = '\0'; r = 0; } //this part is for error handling
            sb3.insert(0, c);
        }
        if (r == 1) sb3.insert(0, "1");

     return sb3.toString();
    }
    public String addBinary(String a, String b)
    {
        return add(a, b);
    }
}

Answer 3

I also learned this method from other and here's the code and some of my comments

public String addBinary(String a, String b) {
    int m = a.length();
    int n = b.length();
    int carry = 0;
    String res = "";
    // the final length of the result depends on the bigger length between a and b, 
    // (also the value of carry, if carry = 1, add "1" at the head of result, otherwise)
    int maxLen = Math.max(m, n);
    for (int i = 0; i < maxLen; i++) {
        // start from last char of a and b
        // notice that left side is int and right side is char
        // so we need to  minus the decimal value of '0'
        int p = i < m ? a.charAt(m - 1 - i) - '0' : 0;
        int q = i < n ? b.charAt(n - 1 - i) - '0' : 0;
        int tmp = p + q + carry;
        carry = tmp / 2;
        res = tmp % 2 + res;
    }
    return (carry == 0) ? res : "1" + res;
}

Answer 4

I got a straightforward solution on this, purely char comparison and string concatenation. This is in python.

class Solution:
# @param a, a string
# @param b, a string
# @return a string
def addBinary(self, a, b):
    if a is None or b is None:
        return None
    r = ''
    zero = '0'
    one = '1'
    carry = zero        # either 0 or 1
    i = -1          # index starts from the right
    while i >= max(len(a), len(b)) * -1 or carry != zero:
        if i < len(a) * -1:
            ca = zero
        else:
            ca = a[i]
        if i < len(b) * -1:
            cb = zero
        else:
            cb = b[i]
        temp = carry + ca + cb      # a string
        if temp in ['000']:
            carry = zero
            r = zero + r
        elif temp in ['001', '010', '100']:
            carry = zero
            r = one + r
        elif temp in ['011','101','110']:
            carry = one
            r = zero + r
        else:
            carry = one
            r = one + r
        i -= 1
    return r