Binary addition with strings

Question

The following method will add two strings of any length as binary numbers assuming the characters 1 and 0. I made this for fun in my spare time. Improvements are not critical but I would like to hear them. I would also like to know if there is a more efficient algorithm to simulate a ALU.

static string BinAdd(string a, string b)
{
    if (a.Length < b.Length)
    {
        string c = a;
        a = b;
        b = c;
    }

    StringBuilder sb = new StringBuilder(a.Length);

    bool addLeft = false;

    for (int i = a.Length - 1, j = b.Length - 1; i >= 0; i--, j--)
    {
        char c = '1';
        bool add = addLeft;
        addLeft = false;

        if (j >= 0)
        {
            if (a[i] == '1' && b[j] == '1')
            {
                c = '0';
                addLeft = true;
            }
            else if (a[i] == '0' && b[j] == '0')
            {
                c = '0';
            }
            else if (add)
            {
                addLeft = true;
            }
        }
        else
        {
            if (a[i] == '0')
            {
                c = '0';
            }
            else if (add)
            {
                addLeft = true;
            }
        }

        sb.Append(add ? (c == '1' ? '0' : '1') : c);
    }

    if (addLeft)
    {
        sb.Append('1');
    }

    char[] cx = new char[sb.Length];
    sb.CopyTo(0, cx, 0, sb.Length);
    Array.Reverse(cx);

    return new string(cx);
}

I'm aware that no validation is done, but I didn't intend to.

Answer 1

It's clear from your code that the length of the sum is at most a.Length + 1, so we can do away with the StringBuilder, copying to a char[], and reversing.

public static string BinAdd(string a, string b)
{
    if (a.Length < b.Length)
    {
        string c = a;
        a = b;
        b = c;
    }

    var sum = new char[a.Length + 1];
    bool addLeft = false;

    for (int i = a.Length - 1, j = b.Length - 1, k = sum.Length - 1; i >= 0; i--, j--, k--)
    {
        char c = '1';
        bool add = addLeft;
        addLeft = false;

        if (j >= 0)
        {
            if (a[i] == '1' && b[j] == '1')
            {
                c = '0';
                addLeft = true;
            }
            else if (a[i] == '0' && b[j] == '0')
            {
                c = '0';
            }
            else if (add)
            {
                addLeft = true;
            }
        }
        else
        {
            if (a[i] == '0')
            {
                c = '0';
            }
            else if (add)
            {
                addLeft = true;
            }
        }

        sum[k] = add ? (c == '1' ? '0' : '1') : c;
    }

    if (addLeft)
    {
        sum[0] = '1';
        return new string(sum);
    }

    return new string(sum, 1, sum.Length - 1);
}

Now the logic inside the loop can be simplified. We're adding three bits, setting one bit of sum, and calculating the carry.

public static string BinAdd(string a, string b)
{
    if (a.Length < b.Length)
    {
        string c = a;
        a = b;
        b = c;
    }

    var sum = new char[a.Length + 1];
    var carry = 0;

    for (int i = a.Length - 1, j = b.Length - 1, k = sum.Length - 1; i >= 0; i--, j--, k--)
    {
        int sumBits = (a[i] - '0') +
                      (j >= 0 ? b[j] - '0' : 0) +
                      carry;
        sum[k] = (char)(sumBits % 2 + '0');
        carry = sumBits > 1 ? 1 : 0;
    }

    if (carry > 0)
    {
        sum[0] = '1';
        return new string(sum);
    }

    return new string(sum, 1, sum.Length - 1);
}

Finally, I would recommend renaming BinAdd to AddBinary, and using @svick's suggestion of

if (a.Length < b.Length)
{
    return AddBinary(b, a);
}

Edit From your comment, you don't want to use an int to sum the bits. In that case, let's look at the addition table

carry x y
    0 0 0 | 0 0
    0 0 1 | 0 1
    0 1 0 | 0 1
    0 1 1 | 1 0
    1 0 0 | 0 1
    1 0 1 | 1 0
    1 1 0 | 1 0
    1 1 1 | 1 1

From that, we can derive the following code

public static string BinAdd(string a, string b)
{
    if (a.Length < b.Length)
    {
        string c = a;
        a = b;
        b = c;
    }

    var sum = new char[a.Length + 1];
    bool carry = false;

    for (int i = a.Length - 1, j = b.Length - 1, k = sum.Length - 1; i >= 0; i--, j--, k--)
    {
        char x = a[i];
        char y = j >= 0 ? b[j] : '0';

        if (carry)
        {
            sum[k] = x == y ? '1' : '0';
            carry = x == '1' || y == '1';
        }
        else
        {
            sum[k] = x == y ? '0' : '1';
            carry = x == '1' && y == '1';
        }
    }

    if (carry)
    {
        sum[0] = '1';
        return new string(sum);
    }

    return new string(sum, 1, sum.Length - 1);
}

Answer 2

strings of any length as binary numbers

Why are they strings? Something like bool[] would fit much better and it would also make your code simpler.

---

string a, string b

Those are not very good names. maybe use something like left and right or first and second?

---

In production code, you should verify that parameters fit your requirements (in your case, that the string contains only '0's and '1's) and throw an exception otherwise.

---

if (a.Length < b.Length)
{
    string c = a;
    a = b;
    b = c;
}

A simpler way to write this would be to use recursion:

if (a.Length < b.Length)
{
    return BinAdd(b, a);
}

---

bool addLeft = false;

A better name for this variable would be carry.

---

char c = '1';
bool add = addLeft;
addLeft = false;

if (j >= 0)
{
    if (a[i] == '1' && b[j] == '1')
    {
        c = '0';
        addLeft = true;
    }
    else if (a[i] == '0' && b[j] == '0')
    {
        c = '0';
    }
    else if (add)
    {
        addLeft = true;
    }
}
else
{
    if (a[i] == '0')
    {
        c = '0';
    }
    else if (add)
    {
        addLeft = true;
    }
}

sb.Append(add ? (c == '1' ? '0' : '1') : c);

All this logic could be simplified by a lot by using a variable to count the ones (including carry). Something like (not tested):

int sum = 0;

if (j >= 0 && b[j] == '1')
    sum++;

if (a[i] == '1')
    sum++;

if (addLeft)
    sum++;

sb.Append(sum % 2);

addLeft = sum / 2 == 1;

---

char[] cx = new char[sb.Length];
sb.CopyTo(0, cx, 0, sb.Length);
Array.Reverse(cx);

return new string(cx);

Instead of this, you could start with List<char> instead of StringBuilder, Reverse() that and then create a string out of it (possibly using string.Join(null, digits), assuming you name the list digits).

Answer 3

I would say that the logic in your code is a little convoluted, and the reason for that is that you are dealing with data a two different levels of abstraction. In one place, you are trying to both manipulate character arrays and perform a bit addition operation. I think it would make it much clearer if you separated these components apart.

public static string BinAdd(string a, string b) {
    if (a.Length < b.Length) {
        return BinAdd(b, a);
    }

    char[] result = new char[a.Length + 1];
    bool carry = false;

    for (int i = a.Length - 1, j = b.Length - 1; i >= 0; i--, j--) {
        result[i + 1] = AddBits(a[i], (j >= 0 ? b[j] : '0'), ref carry);
    }

    if(carry) {
        result[0] = '1';
    }

    return new string(result);
}

private static char AddBits(char a, char b, ref bool carry) {
    if(a != b) {
        return carry ? '0' : '1';
    }

    bool originalCarry = carry;
    carry = a == '1';
    return originalCarry ? '1' : '0';
}

In the above version, I've replaced the StringBuilder with a char array to get away from the data structure juggling (as first seen in mjolka's answer). I avoid needing to define a third variable in the loop since we know that a[i] corresponds to result[i + 1]. I've extracted all the bit adding and carrying into a separate method. Since you are writing in C#, I am able to use a ref parameter for sending in and getting out carry. Were I using a language without this feature, I would have split it into two methods, one to perform the addition, and one to determine if a carry resulted. If their lengths are not equal, we pass in a '0' char. The AddBits method performs some very simple logic to determine the sum and carry, and returns both (the sum directly and the carry through the ref parameter).

Because I've extracted out the AddBits method, I would now be equally capable of writing a method that accepts boolean arrays, strings, char arrays, int arrays, enums, etc., since the outer method handles organizing the data, and only needs to provide proper inputs into the new method. We've improved re-usability while reducing the responsibilities of the code units.