Implement a function that performs binary additi

Interview Questions

Implement a function that performs binary addition .....

Microsoft Interview Questions and Answers

41. Implement a function that performs binary addition .....

Question:
Implement a function that performs binary addition. Input to the function is two const strings. The function returns a string that holds the result of addition.
char* binaryadd(const char* a, const char* b) { }
Eg. "1001"+"101"="1110"

maybe an answer1:

char* binaryadd(const char* firstStr, const char* secondStr)
{
if (NULL == firstStr || NULL == secondStr)
return NULL;

int len = max(strlen(firstStr),strlen(secondStr));
char *outBuf = new char[len+2];
outBuf[len+1] = 0;

char *psecond = (char*)secondStr+strlen(secondStr)-1;
char *pfirst = (char*)firstStr+strlen(firstStr)-1;
char *poutBuf = outBuf+len;
int tmp = '0';
int subsum = 0;
while (pfirst >= firstStr && psecond >= secondStr)
{
subsum = *pfirst + *psecond + tmp;
switch (subsum)
{
case '0'+'0'+'0':
*poutBuf = '0';
tmp = '0';
break;
case '0'+'0'+'1':
*poutBuf = '1';
tmp = '0';
break;
case '0'+'1'+'1':
*poutBuf = '0';
tmp = '1';
break;
case '1'+'1'+'1':
*poutBuf = '1';
tmp = '1';
break;
default:
return NULL;
}
poutBuf--;
pfirst--;
psecond--;
}
char *pless = NULL;
const char *lessPar = NULL;
if (pfirst >= firstStr)
{
pless = pfirst;
lessPar = firstStr;
}
else if (psecond >= secondStr)
{
pless = psecond;
lessPar = secondStr;
}

if (NULL != pless)
{
while (pless >= lessPar)
{
subsum = *pless + tmp;
switch (subsum)
{
case '0'+'0':
*poutBuf = '0';
tmp = '0';
break;
case '0'+'1':
*poutBuf = '1';
tmp = '0';
break;
case '1'+'1':
*poutBuf = '0';
tmp = '1';
break;
default:
return NULL;
}
poutBuf--;
pless--;
}
}

if ('1' == tmp)
{
*poutBuf = '1';
return poutBuf;
}
else
return poutBuf+1;

maybe an answer2:

import java.util.Collections;
import java.util.LinkedList;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
* @author xxx
* implement a function that performs binary addition. Input to the
* function is two const strings. The function returns a string that
* holds the result of addition.
*/
public class M09BinaryAdd {

static final char[] bv = { '0', '1' };

/**
* @param a
* first binary number
* @param b
* second binary number
* @return
*/
public static String addBinary(char[] a, char[] b) {
// Checks input parameter

if (a == null || b == null || a.length < 1 || b.length < 1)
throw new IllegalArgumentException("Empty numbers");

Pattern p = Pattern.compile("(0|1)*");
String st = new String(a);
Matcher matcher = p.matcher(st);
if(matcher.find()) {
if(!st.substring(matcher.start(), matcher.end()).equals(st)) {
throw new IllegalArgumentException("Argument 1 is not a binary string");
}
}
st = new String(b);
matcher = p.matcher(st);
if (matcher.find()) {
if(!st.substring(matcher.start(), matcher.end()).equals(st)) {
throw new IllegalArgumentException("Argument 2 is not a binary string");
}
}
LinkedList<Character> r = new LinkedList<Character>();
int ia = a.length - 1;
int ib = b.length - 1;
int caryFlag = 0;
while (ia >= 0 && ib >= 0) {

int s = (a[ia] - '0') ^ (b[ib] - '0');
if (caryFlag == 1) {
s ^= caryFlag;
}
r.add(bv[s]);
caryFlag = (a[ia] - '0') & (b[ib] - '0');
ia--;
ib--;
}

while (ia >= 0) {
int s = a[ia] - '0';
if (caryFlag == 1) {
s ^= caryFlag;
}
r.add(bv[s]);
caryFlag &= a[ia] - '0';
ia--;
}

while (ib >= 0) {
int s = a[ib] - '0';
if (caryFlag == 1) {
s ^= caryFlag;
}
r.add(bv[s]);
caryFlag &= a[ib] - '0';
ib--;
}
if (caryFlag == 1) {
r.add(bv[1]);
}
Collections.reverse(r);
StringBuffer sb = new StringBuffer();
for (Character c : r) {
sb.append(c);
}
return sb.toString();
}

/**
* @param args
*/
public static void main(String[] args) {
char[] a = { '1', '0', '0', '1','0' };
char[] b = { '1', '0', '1' };
String r = addBinary(a, b);
System.out.println(r);
}

}

(Continued on next question...)