3
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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);
}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 1. You are right, using char[] would be much better. 2. I'm aware that integers could be used, but it would beat the challenge. 3. I prefer brevity for this stuff, like I would name a method Xor instead of ExclusiveOr. 4. I'm not too comfortable with recursion for operations which lack complexity, but I will definitely think it over. \$\endgroup\$ – Leopold Asperger Jul 20 '14 at 4:44
  • \$\begingroup\$ Note that your method will always create the final string starting at index 1, I believe this is a bug. \$\endgroup\$ – Leopold Asperger Jul 20 '14 at 4:50
  • \$\begingroup\$ @LeopoldAsperger please re-read code, if carry > 0 we return new string(sum). \$\endgroup\$ – mjolka Jul 20 '14 at 5:28
2
\$\begingroup\$

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).

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 1. I used a string because it looks better and bool should be used to indicate logic, not numbers. 2. I think a and b are fine, left and right imply that there is an operator involved, which is not the case. 3. I agree that arguments should be checked. 4. I haven't thought of recursion, nice find, it seems like a hack though. 5. The name carry makes sense of course, but it wasn't abstract enough for my taste. \$\endgroup\$ – Leopold Asperger Jul 20 '14 at 4:30
  • \$\begingroup\$ 6. Using integers kind of beats the purpose of simulating binary addition, but I get the idea. 7. I'd like to stick with StringBuilder, it does what it should within the right context. \$\endgroup\$ – Leopold Asperger Jul 20 '14 at 4:31
0
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ You are only supposed to derive a new instance method when it can be used by multiple other members. Methods should not be used to abstract, thats what polymorphism is for. \$\endgroup\$ – Leopold Asperger Jul 22 '14 at 7:02
  • \$\begingroup\$ Is that a rule of this paticular problem or a personal rule of yours? I only ask because I have never heard that before, and have instead seen helper methods created exclusively to simplify an algorithm and make a method more readable, even if used only in one place. \$\endgroup\$ – cbojar Jul 22 '14 at 13:55
  • \$\begingroup\$ No, this is programmer common sense. When you define a method, you encapsulate behavior which can be called from multiple places. But what you are doing is unthoughtful, there is absolutely no indication that you will ever need to reuse the addbits method again. Petty abstractions are just as bad as no abstractions at all. \$\endgroup\$ – Leopold Asperger Jul 22 '14 at 17:33
  • \$\begingroup\$ I guess I don't know much about programmer common sense. I rely on precepts such as SOLID instead. Here, I split a method with two responsibilities into a public method and a helper method so I could make them both more single responsibility. You say this code will never need reused, but there is never a guarantee of that in production. Alternatively, if this is just a code challenge, why not just shove all the code into main? Isn't it just a useless abstraction? \$\endgroup\$ – cbojar Jul 22 '14 at 18:26
  • \$\begingroup\$ Well there is no perfect set of OOP design principles, OOP is too high-level. What matters most is that others can relate to your code, second is that you do what you think is right. Ontopic; your method will never be reused, as the name AddBits implies, it is used for addition, and there is obviously only one kind of addition operation, and so only one addition method. This confirms my point about bad abstractions. And you're pulling my leg with that last comment, defining a method for an operation, any operation, is a sane thing to do, challenge or not. \$\endgroup\$ – Leopold Asperger Jul 22 '14 at 18:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.