Interview Question

Software Engineer Intern Interview(Student Candidate) Palo Alto, CA

Write a function that takes in two binary strings and

  returns their sum (also a binary string).
Answer

Interview Answer

2 Answers

2

// let A[1..n] n B[1..m] be the two strings and the result is to be stored in S[]

if(n>m)
      k=n;
else
      k=m;
C=0;
for(i=n, j=m; i>0 !! j>0; i--, j--)
{
   if(i<=0) { i=0; A[0]=0}
  if(j<=0) { j=0; B[0]=0}
    count=0;
      if(A[i]==1)
           count++;
      if(B[j]==1)
           count++;
      if(C==1)
            count++;

      switch(count)
       { case 0 : S[k]=0; C=0;
                            break;
             case 1 : S[k]=1; C=0;
                             break;
             case 2 : S[k]=0; C=1;
                              break;
             case 3 : S[k]=1; C=1;
                              break;
         }
         k--;
}

rj on Nov 19, 2011
0

#include <string>
#include <cmath>

using namespace std;

string findBinSum(string a, string b) {
/*
    Iterate through strings and find integer values.
    Find sum. Convert sum back to binary string.
*/
    int sizeA = a.size();
    int sizeB = b.size();
    int valA =0;
    int valB =0;
    for (int i=sizeA-1; i >= 0;i--)
    {
        if (a[i] == '1') {
            valA += (int)pow((double)2,(double)(sizeA-1-i));
        }
    }
    for (int k=sizeB-1; k >= 0;k--)
    {
        if (b[k] == '1') {
            valB += (int)pow((double)2,(double)(sizeB-1-k));
        }
    }
    cout << "valA = " << valA << endl;
    cout << "valB = " << valB << endl;

    int sum = valA + valB;
    if (sum == 0) {string answer = "0"; return answer; }
    cout << "the sum is " << sum << endl;

    int power = (int)(log(sum)/log(2));
    cout << "the power is " << power << endl;
    int numUsed = (int)pow((double)2,(double)power);
    sum -= numUsed;
    string answer = "1";
    for(int j=power-1; j>=0; j--) {
        numUsed = (int)pow((double)2,(double)j);
        if ( sum-numUsed >= 0) {
            sum -= numUsed;
            answer += "1";
        }
        else {
            answer += "0";
        }
    }
    return answer;
}

int main(){
    string binary1 = "1011";
    string binary2 = "1011";

    string answer = findBinSum(binary1,binary2);
    cout << "sum: " << answer << endl;
}

Tim on Dec 21, 2011

Add Answers or Comments

To comment on this Question, Sign In with Facebook or Sign Up