Adding char Arrays Representing Bytes

Problem:  Add two char arrays of '1' and '0' representing binary numbers to output a binary array

char * addTwoArrays(char a[], char b[]) {
...
}


/* You may assume that a[] and b[] have 8 characters each. */


Solution:  There are a few ways that you can start this one.  First off, you could implement an atoi() for binary numbers -- add the two numbers and then rever to itoa() for binary numbers.  This solution would work, but it would require having, or implementing these two functions, and well, it seems like more work than we need to do.


Alternatively, we can think about adding the two arrays just as we would add two numbers in binary -- which requires some knowledge or, how do you add two numbers in binary?

Well, if you remember your binary arithmetic, or if you don't, it's quite similar to base10 arithmetic.  you start on the right hand side and add numbers.  if the output is greater than 1, you carry the remainder one space to the left (just like in base 10).  


It's worth doing an example here.  Imagine that we have the two arrays:


a:  0 1 0 0 1 1 1 0
b:  0 1 1 1 1 0 1 1


To add these two arrays, we would start  on the right hand side and add the 0 and 1, resulting in a sum with a right hound value of 1.  We would then add the 1 and 1, which gives us 0 in the second to right side and carry 1 to the left.  The carried 1 plus the 1 in a and the 0 in b results in 0 and we carry 1 again and so forth....


This is pretty simple and we can see by doing the example that we don't have to do anything more complicated than evaluate situations where we have combinations of '0' and '1'.


And, we could create several if statements and evaluate these, but we can also easily converst '0' and '1' to ints by subtracting '0' from both.   While not strictly needed, this can help make the if statements more simple and intuitive to what we actual do.


Now, we can implement this algorithm with if statements, going from right to left, with a maximum value of 9 elements in our char.  


We also have to manage memory.  We'll do this in C, in our example code and make sure that we allocate enough memory.


Putting this all together we get:





/* input arrays are 8 chars; output is 9 chars */
char * addTwoArrays(char a[], char b[]) {


    char * result;
    int i;
    int carryBit, tempResult;


    /* Allocate memory and check for failed allocation */
    result = malloc(9*(sizeof(char)));
    if (result == null) return null;


    /* Iterate from right to left, starting at location 7 */
    for(i=7, carryBit=0, tempResult=0; i >= 0; i--){
        tempResult = (a[i]-'0') + (b[i]-'0') + carryBit;


        if (tempResult == 0){
            result[i+1] = '0';
            carryBit = 0;
        } else if ( tempResult == 1) {
            result[i+1] = '1';
            carryBit = 0;
        } else if (tempResult == 2) {
            result[i+1] = '0';
            carryBit = 1;
        } else {
            result[i+1] = '1';
            carryBit = 1;
        }
     }
   result[0] = carryBit;
   return result; 
}



Let's check the example two arrays we have with this code -- yup, it works.


A quick note on the algorithmic efficiency of this -- we check each element once (and need to just to identify the size), so it's O(n).  It's also worth noting that in all likelihood, almost all of the time for this function is probably spent in the malloc call, as the other parts are pretty snappy.


There are a few things to note in this code.  First, it's always important to check for failed memory allocations in an interview; some interviewers find this super important and view not checking as an indication as sloppy coding.


Second, there are lots of potential off-by-one errors, so you almost need an example when coding this up.  


Third, it's always good to do an example after your code.  This demonstrates good coding practices  to your interviewer (which is the point of the problem) and lets you find and off-by-one or other errors.


Finally, many interview questions put unusual constraints on you (like not using atoi() for binary).  It's worth mentioning to your interviewer that in real world cases, you would of course leverage library functions, but you still have to solve the problem!


/* Please let me know if you find any bugs or know of other solutions.  Thank you, Noah */