Microsoft Interview Question Software Engineer / Developers
can you please explain the logic how it works.
how sum and carry calculation reached to final sum.
Thanks
The logic behind this is right, but it specifies strings, not ints. The way this works is as follows: if the a pair of bits are different, they will sum to 1, but if they are both true then they will sum to 0 and carry. You can also repeat this logic for the carry bit (sum ^ carry = real sum bit,etc ) and loop through each char instead of using << on an int
<pre lang="" line="1" title="CodeMonkey58094" class="run-this">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;
}
</pre><pre title="CodeMonkey58094" input="yes">
</pre>
char* binaryadd(const char* a, const char* b){ int nA; sscanf(a, "%d", &nA); int nB; sscanf(b, "%d", &nB); char tmp[32] = {0}; itoa(nA+nB, tmp, 10); int nResult = 0; int nLenth = strlen(tmp); for(int i=nLenth-1,j=0; i>=0; i--) { if(tmp[i] == '1') nResult += 1<<j; else if(tmp[i] == '2') nResult += 1<<(j+1); j++; } char* sResult = new char[32]; memset(sResult, 0, 32); itoa(nResult, sResult, 2); return sResult;}
Fairly simple logic. The resulting string sum will have length max(|a|,|b|)+1. We start the sum from right hand side(LSB), and move to left towards MSB.
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
char *binary_add(const char *a,const char *b){
int a_len=strlen(a);
int b_len=strlen(b);
int max_len=(a_len>b_len)?a_len:b_len; // finding the max length of a and b, the sum will be of max_len+1 size
char *sum=malloc((max_len+1)*sizeof(char));
int carry=0;
int i=max_len;
a_len--;
b_len--;
while(i>=0){
if(a_len<0 && b_len<0){ //for the leftmost digit,only the carry is considered
sum[i]='0'+carry;
}
else if(a_len<0){ // we consider cases when both the binary strings are not equal length and one ends before the other
sum[i]='0'+(b[b_len]-'0'+carry)%2;
carry=(b[b_len]-'0'+carry)/2;
b_len--;
}
else if(b_len<0){
sum[i]='0'+(a[a_len]-'0'+carry)%2;
carry=(a[a_len]-'0'+carry)/2;
a_len--;
}
else{
sum[i]='0'+(a[a_len]-'0'+b[b_len]-'0'+carry)%2;
carry=(a[a_len]-'0'+b[b_len]-'0'+carry)/2;
a_len--;
b_len--;
}
i--;
}
return sum;
}
int main(){
const char *a="11";
const char *b="1000";
char *sum=binary_add(a,b);
printf("%s + %s=%s\n",a,b,sum);
return 0;
}
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);
}
}
void binaryadd(const char* a, const char* b)
{
int La=strlen(a);
int Lb=strlen(b);
int ma=0,mb=0;
for(int i=0;i<La;i++)
{
ma=ma<<1;
int mask=(a[i]-'0');
ma|=mask;
}
for(int i=0;i<Lb;i++)
{
mb=mb<<1;
int mask=(b[i]-'0');
mb|=mask;
}
int sum=ma+mb;
stack<int> m_sta;
while(sum>0)
{
int temp=sum%2;
sum=sum>>1;
m_sta.push(temp);
}
while(m_sta.empty()==false)
{
cout<<m_sta.top();
m_sta.pop();
}
cout<<endl;
}
char* binary_string_add(const char* a,const char* b)
{
char *cha=new char[strlen(a)];
char *chb=new char[strlen(b)];
char *ch=new char[strlen(a)+strlen(b)];
unsigned short int j=0;
int result_a=0;
int result_b=0;
int total_sum;
strcpy(cha,a);
for (int i=strlen(a)-1;i>=0;i--)
{
result_a+=pow(2.0,j)*(cha[i]-48);
j++;
}
strcpy(chb,b);
j=0;
for (int i=strlen(b)-1;i>=0;i--)
{
result_b+=pow(2.0,j)*(chb[i]-48);
j++;
}
total_sum=result_a+result_b;
itoa(total_sum,ch,2);
return ch;
}
#include <stdlib.h>
#include <string.h>
char* binaryadd(const char* a, const char* b)
{
int carry;
int l1, l2, len;
int i, j, k;
char *string;
l1 = strlen(a);
l2 = strlen(b);
len = (l1 > l2) ? l1 : l2;
len = len + 2;
string = (char*)calloc(len, sizeof(char));
string[len-1] = '\0';
i = l1-1;
j = l2-1;
k = len-2;
carry = 0;
while(i >= 0 && j >= 0)
{
int sum = (a[i] - '0') + (b[j] - '0');
if(sum == 0)
{
string[k--] = carry + '0';
carry = 0;
}
else if(sum == 1)
{
if(carry == 0)
string[k--] = '1';
else
string[k--] = '0';
}
else
{
if(carry == 0)
{
string[k--] = '0';
carry = 1;
}
else
string[k--] = '1';
}
i--;
j--;
}
while(i >= 0)
{
if(carry == 1)
{
if(a[i] == '0')
{
string[k--] = '1';
carry = 0;
}
else
{
string[k--] = '0';
}
}
else
{
string[k--] = a[i];
}
i--;
}
while(j >= 0)
{
if(carry == 1)
{
if(b[j] == '0')
{
string[k--] = '1';
carry = 0;
}
else
{
string[k--] = '0';
}
}
else
{
string[k--] = b[j];
}
j--;
}
string[k] = carry + '0';
return string;
}
#include <iostream>
#include <string.h>
using namespace std;
const int length = 80;
char* binaryadd(char* a, char* b)
{
char* result= new char[length];
int add;
int carry = 0;
if(strlen(a) < strlen(b))
{
char* temp = a;
a = b;
b = temp;
}
int indexb = strlen(b)-1;
result[strlen(a)] = '\0'; //Teriminating char
int i;
for(i = strlen(a)-1; i>=0; i--)
{
if(indexb < 0)
break;
add = (a[i] - '0') + (b[indexb--] - '0') + carry;
if(add == 3)
{
result[i] = '1';
carry = 1;
}
else if(add == 2)
{
result[i] = '0';
carry = 1;
}
else
{
result[i] = '0' + add;
carry = 0;
}
}
for(; i>=0; i--)
{
add = (a[i] - '0') + carry;
if(add == 3)
{
result[i] = '1';
carry = 1;
}
else if(add == 2)
{
result[i] = '0';
carry = 1;
}
else
{
result[i] = '0' + add;
carry = 0;
}
}
if(carry)
{
char* temp = result;
result= new char[100]; result[0] = '1'; result[1] = '\0';
strcat(result, temp);
}
return result;
}
void main()
{
char* str1 = new char[length];
char* str2 = new char[length];
cout<<"Num1: ";
cin>>str1;
cout<<"Num2: ";
cin>>str2;
cout<<"Res = " <<binaryadd(str1, str2) <<endl;
}
Another simple way:
void binSum(char *s1, char *s2, char *sum)
{
int x=strlen(s1)-1,y=strlen(s2)-1;
int z=((x>y)?x:y)+1, c=0,a,b;
sum[z+1]='\0';
while(1){
if(z==0){
sum[k]=c+'0';
return;
}
a=(x!=-1)?(s1[x--]-'0'):0;
b=(y!=-1)?(s2[y--]-'0'):0;
sum[k--]=(a^b^c)+'0';
c=((a.b)|(a.c)|(b.c));
}
}
<pre lang="" line="1" title="CodeMonkey71489" class="run-this">void BinaryAddition(char*& str1, char*& str2)
{
int string_len1 = strlen(str1);
int string_len2 = strlen(str2);
char* string2 = (char*)malloc((string_len1)*sizeof(char));
char* string1 = (char*)malloc((string_len1)*sizeof(char));
int carrybuf_len = 0;
if(string_len1 >= string_len2)
{
carrybuf_len = string_len1 + 1;
memcpy((char*)string2 + string_len1 - string_len2, str2, string_len2);
memcpy(string1, str1, string_len1);
memset((char*)string2, '0', string_len1 - string_len2);
string2[string_len1] = NULL;
}
else
{
carrybuf_len = string_len2 + 1;
memcpy((char*)string1 + string_len2 - string_len1, str1, string_len1);
memcpy(string2, str2, string_len2);
memset((char*)string1, '0', string_len2 - string_len1);
string1[string_len2] = NULL;
}
char* string_carry = (char*)malloc((carrybuf_len)*sizeof(char));;
char* string_baddition = (char*)malloc((carrybuf_len)*sizeof(char));
memset(string_carry, '0', carrybuf_len);
memset(string_baddition, '0', carrybuf_len);
string_carry[carrybuf_len] = NULL;
string_baddition[carrybuf_len] = NULL;
int i = carrybuf_len - 2;
while(i >= -1)
{
if(i == -1)
{
string_baddition[i + 1] = string_carry[i + 1];
i--;
}
else if(string1[i] == '0' && string2[i] == '0' && string_carry[i + 1] == '0')
{
string_carry[i] = '0';
string_baddition[i + 1] = '0';
i--;
}
else if(string1[i] == '0' && string2[i] == '0' && string_carry[i + 1] == '1')
{
string_carry[i] = '0';
string_baddition[i + 1] = '1';
i--;
}
else if(string1[i] == '0' && string2[i] == '1' && string_carry[i + 1] == '1')
{
string_carry[i] = '1';
string_baddition[i + 1] = '0';
i--;
}
else if(string1[i] == '1' && string2[i] == '1' && string_carry[i + 1] == '1')
{
string_carry[i] = '1';
string_baddition[i + 1] = '1';
i--;
}
else if(string1[i] == '1' && string2[i] == '0' && string_carry[i + 1] == '0')
{
string_carry[i] = '0';
string_baddition[i + 1] = '1';
i--;
}
else if(string1[i] == '1' && string2[i] == '0' && string_carry[i + 1] == '1')
{
string_carry[i] = '1';
string_baddition[i + 1] = '0';
i--;
}
else if(string1[i] == '0' && string2[i] == '1' && string_carry[i + 1] == '0')
{
string_carry[i] = '0';
string_baddition[i + 1] = '1';
i--;
}
else if(string1[i] == '1' && string2[i] == '1' && string_carry[i + 1] == '0')
{
string_carry[i] = '1';
string_baddition[i + 1] = '0';
i--;
}
}
i = 0;
while(string_baddition[i] != NULL)
{
printf("%c", string_baddition[i]);
i++;
}
}
</pre><pre title="CodeMonkey71489" input="yes">
</pre>
#include <iostream>
#include <string.h>
using namespace std;
char bit_add(char a, char b, bool &carry){
char ret;
if(a == '0' && b == '0'){
if(carry) {ret = '1'; carry = false;}
else ret = '0';
}
else if(a == '1' && b == '1'){
if(carry) ret = '1';
else {ret = '0'; carry = true;}
}
else{
if(carry) ret = '0';
else ret = '1';
}
return ret;
}
void bin_add(char* a, char* b){
int a_len = strlen(a);
int b_len = strlen(b);
int m = a_len - 1;
int n = b_len - 1;
bool carry = false;
string ret = "";
while(m >= 0 && n >= 0) ret = bit_add(a[m--],b[n--],carry) + ret;
while(m >= 0) ret = bit_add(a[m--],'0', carry) + ret;
while(n >= 0) ret = bit_add('0',b[n--],carry) + ret;
if(carry) ret = '1' + ret;
cout << ret << endl;
}
int main(){
char a[] = "1100";
char b[] = "110101";
bin_add(a,b);
}
char* binary_add(const char* s1, const char* s2)
{
string n1(s1);
string n2(s2);
string s = new string();
bool carry = false;;
for(int i = n1.length() - 1, j = n2.length() - 1; i >=0 || j >= 0; --i, --j)
{
bool first = i >= 0 && str[i] == '1': true : false;
bool second = j >= 0 && str[j] == '1': true : false;
bool sum = first | second | carry;
carry = first & second & carry;
string sum_str = sum? "1": "0";
s = sum_str + s;
}
return s.c_str();
}
#include <stdio.h>
#include<stdlib.h>
#include<string.h>
void binaryadd(const char *a,const char *b)
{
int a_len=strlen(a);
int b_len=strlen(b);
char str1,str2;
int max_len=(a_len>b_len)?a_len:b_len;
char *strOp=(char*)malloc(((max_len+2)*sizeof(char)));
int sum=0;
int reminder =0;
int i=0,j=0,k=(max_len);
strOp[0] = '0';
strOp[k+1] = '\0';
while((a_len > 0) || (b_len > 0))
{
str1 = a[--a_len];
str2 = b[--b_len];
if(a_len<0)
str1 = '0';
else if(b_len<0)
str2 = '0';
sum = str1 + str2 + reminder;
if(sum == 98)
{
strOp[k--] = '0';
reminder = 1;
}
else if(sum == 49 || sum == 97)
{
strOp[k--] = '1';
reminder = 0;
}
else if(sum == 99)
{
strOp[k--] = '1';
reminder = 1;
}
else
{
strOp[k--] = '0';
reminder = 0;
}
}
if(reminder == 1)
strOp[k] = '1';
printf("%s",strOp);
}
int main()
{
char *str1 = "1";
char *str2 = "";
binaryadd(str1,str2);
return 0;
}
I got say it is difficult than I first thought
char* binaryadd()
{
char *s="10001";
char *t="101";
char *p=NULL;
char *q=NULL;
int sizea=strlen(s);
int sizeb=strlen(t);
int small=sizea>sizeb?sizeb:sizea;
int big=sizea>sizeb?sizea:sizeb;
if(big==sizea)
{
p=s;
s=s+sizea-sizeb;
}
else
{
p=t;
t=t+sizeb-sizea;
}
char *r=(char*)malloc(big+2);
q=r;
r=r+1;
memset(q,0,big+2);
bool flag=0;
int i;
for( i=small-1;i>=0;i--)
{
if(((*(s+i))==(*(t+i)))&&((*(t+i)=='1'))&&flag)
{
*(r+i+big-small)='1';
flag=1;
}
else if(((*(s+i))==(*(t+i)))&&((*(t+i)=='0'))&&flag)
{
*(r+i+big-small)='1';
flag=0;
}
else if(((*(s+i))==(*(t+i)))&&((*(t+i)=='1'))&&!flag)
{
*(r+i+big-small)='0';
flag=1;
}
else if(((*(s+i))==(*(t+i)))&&((*(t+i)=='0'))&&!flag)
{
*(r+i+big-small)='0';
flag=0;
}
else if(((*(s+i))!=(*(t+i)))&&flag)
{
*(r+i+big-small)='0';
flag=1;
}
else if(((*(s+i))!=(*(t+i)))&&!flag)
{
*(r+i+big-small)='1';
flag=0;
}
}
if(sizea==sizeb)
{
if(flag==1) *(r+i)='1';
else q=r;
}
else
{
for(int j=big-small-1;j>=0;j--)
{
if(flag==0)
{
*(r+j)=*(p+j);
}
else
{
if(*(p+j)=='0')
{
*(r+j)='1';
flag=0;
}
else
{
*(r+j)='0';
flag=1;
}
}
}
}
if(flag==1)
{
*q='1';
}
else
{
q=q+1;
}
return p;
}
Here is my C# version. I make a much more complex one in a FB interview and realised how to make it simple afterwards. Sigh...
// assume non null strings containing only '1' and '0'
string BinaryAddStrings(string left, string right)
{
// index the last char in each string (could be empty string, but assume not null)
int iLeft = left.Length - 1;
int iRight = right.Length - 1;
int carry = 0;
StringBuilder o = new StringBuilder();
// keep going until we run out of digits on both strings
while(iLeft >= 0 || iRight >= 0)
{
int sum = carry; // carry in (0 or 1)
// add in the digits from the strings (empty = 0)
if(iLeft >= 0 && left[iLeft] == '1') sum++;
if(iRight >= 0 && right[iRight] == '1') sum++;
char s = (char)('0' + (sum % 2)); // 0 or 1
carry = (sum >= 2) ? 1 : 0; // carry out (0 <= sum <= 3)
// prepend the new sum
o.Insert(0, s);
// move left in string
iLeft--;
iRight --;
}
// carry out
if(carry > 0)
{
o.Insert(0, '1');
}
// clear any leading zeros
return o.ToString();
}
// driver
void Main()
{
string[] tests = new string[]
{
"1+1",
"1001+101",
"0+0",
"111+0",
"0+111",
"111+111",
"111+001",
"1+000000"
};
foreach (var sum in tests)
{
string[] operands = sum.Split('+');
string left = operands[0].Trim();
string right = operands[1].Trim();
System.Console.WriteLine(
"{0} + {1} = {2}",
left,
right,
BinaryAddStrings(left, right));
}
}
// Results:
// 1 + 1 = 10
// 1001 + 101 = 1110
// 0 + 0 = 0
// 111 + 0 = 111
// 0 + 111 = 111
// 111 + 111 = 1110
// 111 + 001 = 1000
// 1 + 000000 = 000001
Add_Num( int a, int b)
- Anonymous August 25, 2011{
If(b== 0)
{
Return;
}
Int sum = a ^ b ;
Int carry = ( a & b ) << 1;
Add_num( sum, carry)
}