Adding 2 binary strings

Question

I'm passing almost all leetCode tests with this, but not understanding why the output is wrong ("/0") when the input is: a = "10100000100100110110010000010101111011011001101110111111111101000000101111001110001111100001101" b = "110101001011101110001111100110001010100001101011101010000011011011001011101111001100000011011110011" Anyone has an idea to what is not working ? Thanks

#include <stdio.h>
#include <stdlib.h>

char * sumBinary(long int binary1, long int binary2, char * result);

char * addBinary(char * a, char * b)
{
    char * result;
    long int a_int;
    long int b_int;

    a_int = atoi(a);
    b_int = atoi(b);
    result = malloc(sizeof(*result) * 1000);
    if (!result)
        return (NULL);
    sumBinary(a_int, b_int, result);
    return (result);
}

char * sumBinary(long int binary1, long int binary2, char * result)
{
    int i;
    int t;
    int rem;
    int sum[1000];

    i = 0;
    t = 0;
    rem = 0;
    
     if ((binary1 == 0) && (binary2 == 0))
    {
        result[0] = '0';
        result[1] = '\0';
    }  
    else
    {
        while (binary1 != 0 || binary2 != 0)
        {
            sum[i++] = (binary1 %10 + binary2 % 10 + rem) % 2;
            rem = (binary1 %10 + binary2 % 10 + rem) / 2;
            binary1 = binary1 / 10;
            binary2 = binary2 / 10;
        }
        if (rem != 0)
            sum[i++] = rem;
        --i;
        while (i >= 0)
        {
            result[t] = sum[i] + '0'; 
            t++;
            i--;
        }
        result[t] = '\0';
        }
    return (result);
}

Don't work with numbers, but with strings. I think you're supposed to do the addition bit by bit yourself (just like you'd do a binary adiddion with apen and a piece of paper), thus you can add arbitrarily long binary numbers. — Jabberwocky
– Jabberwocky, Commented Oct 12, 2022 at 11:49
b[] is about 100 'bits' long... Not gonna fit that into a typical 32 or 64 bit long int... — user17592432
– user17592432, Commented Oct 12, 2022 at 11:56
thank you @Jabberwocky for your reply. I'm kind of new in C (and on stack overflow as well) and I don't believe I get well your point... I turned strings into int in order to avoid to have to add bit by bit (not sure on how it works) but you're saying that this approach is not working anyway with long binary numbers ? Is there anyway to add long binary numbers without adding bit by bit ? Thanks — bl000m
– bl000m, Commented Oct 12, 2022 at 12:02
thank you @Fe2O3 ! should I use unsigned int better in your opinion ? Or how to get b[] fitting ? — bl000m
– bl000m, Commented Oct 12, 2022 at 12:05
No. You cannot "pack" 100 bits into the usual 'integer' data sizes available. You can 'split' the string into, for instance, 36+32+32 bits and fit each of those into a standard 64bit integer. But, you have to figure out the conversion from 'string' to 'integer' and figure out how to deal with "adding with carry"... Good learning project. Tuck in and go for it... (One piece of the puzzle is to use strtol() instead of atoi()...) Best wishes... — user17592432
– user17592432, Commented Oct 12, 2022 at 12:13

JonGreen · Accepted Answer · 2022-10-12 12:13:36Z

1

For a start, you should be using atol(3), not atoi(3) if you're using long int. But that's not the main issue here.

atol(3) and atoi(3) expect strings containing decimal numbers, not binary, so that's not going to work well for you. You would need strtol(3), which you can tell to expect a string in ASCII binary. But again, this is not the main issue.

You don't give the question text, but I'm guessing they want you to add two arbitrarily-long ASCII-binary strings, resulting in an ASCII-binary string.

I imagine their expectation, given it's arbitrarily-long, is that you would be working entirely in the string domain. So you'd allocate for a string whose length is two greater than the longer of the two you get as parameters (+1 for the terminal NUL, the other +1 for a potential overflow digit).

Then you start from the end, working back to the start, adding the corresponding digits of the parameter strings, placing the results into the result string starting from its end (allowing for that terminal NUL), adding as if you were doing it by hand.

Don't forget to add a leading zero to the result string, if you don't overflow into that position.

Note that I'm not going to write the code for you. This is either a learning exercise or a test: either way, you need to do the coding so you can learn from it.

answered Oct 12, 2022 at 12:13

JonGreen

3791 silver badge5 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

bl000m Over a year ago

thank you so much for your detailed reply, that is really usefull ! I'm training on LeetCode and yes absolutely my goal is not having the solution but a tip on how to better get it, that is what your answer does, thanks. I work on it !

JonGreen Over a year ago

I'm glad I could help, Mathia. If you feel my answer is the best one for you, please mark it as the accepted answer.

Collectives™ on Stack Overflow

Adding 2 binary strings

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related