remove a character by using conditional statement

Question

recently just practiced the problem 67 in Leetcode This problem is like you would be given two binary string, and you have to calculate the sum of these two binary string and return the result.For example a = "11" and b = "1", then the desired result should be output= "100"; if a ="1010" b="1011", then output should be: "10101" The following code is my solution.

#define Max(a,b) ((a > b)? a : b)
char* addBinary(char* a, char* b) {
    
    int carry = 0;
    int lengthA = strlen(a);
    int lengthB = strlen(b);
    char *result = calloc( Max(lengthA, lengthB)+2, sizeof(char) );
    int idx_a = lengthA - 1, idx_b = lengthB -1;
    for( int i = Max(lengthA, lengthB); i >= 0; i-- )
    {
        int bit = carry;
        if(idx_a >= 0) bit += a[idx_a--] -'0';
        if(idx_b >= 0) bit += b[idx_b--] -'0';
        carry = bit>>1; 
        result[i] = (bit%2) + '0';
    }
    
     return result ;
}

The problem is if the test case are a =='0' b =='0', my code would return the '00' this result ,but the desire result is'0'. Well then I looked other solution, I found out if I changed the last line to this:return result+ (result[0] == '0'); then the code would output correct answer, for this part result[0] == '0' ;,I think it is a conditional statement and would return true or false,but I can't understand why it would work and removed the character in result[0]. Could someone please explain the magic behind this .

Answer 1

I think it is a conditional statement and would return true or false…

result[0] == '0' is an expression, not a statement. Specifically, it is an “equality expression.” It does not evaluate to true or false. It evaluates to 1 if the relationship (equality) is true and 0 if the relationship is false.

So, when the first digit of the result (result[0]) is “0”, result + (result[0] == '0') evaluates to result + 1, adding 1 to result. When the first digit is not “0”, it evaluates to result + 0, which is just result.

result + 1 points one array element beyond where result points. So, if result points to, for example, the “a” in “abc”, then result + 1 points to the “b” in “abc”.

So, when result points to “00” followed by a null character, returning result + 1 points to “0” followed by a null character.

However, this is a bad thing to do, because the memory for result is allocated in this routine, and the caller ought to free that memory and needs to know its base address for that. Usually, the address returned by a routine is the base address, so the caller just passes that address to free. When you return result + 1, you return something other than the base address. If the caller passes that to free, the behavior of the program is not defined by the C standard.

An alternative is to add code to the routine: If result[0] is “0”, then change the memory to contain “0” (followed by a null byte) instead of “00” (followed by a null byte), and always return result. Note that you will need to make a similar adjustment for any summation that produces a leading “0” in the space you allocated, such as adding “100” and “10”, for which your code produces “0110”.

Answer 2

Comparison expressions evaluate to 1 or 0 in C, so adding this to the result pointer makes the function return a pointer to the first digit or the second digit if the first is 0. The problem with that is the caller cannot determine if the function returned a pointer to an allocated block of memory or a pointer inside said block so it cannot pass the pointer to free() to release this memory.

If the addition produces a binary number that starts with a 0, you need to copy the contents of the string one byte to the left, which is inefficient but necessary for the caller to be able to free the memory.

Note also some other problems in your code:

• #define Max(a,b) ((a > b)? a : b) is a bad way to define a max function. The macro arguments are not parenthesized so depending on the actual arguments, the resulting expansion may not get evaluated as expected. Furthermore, the arguments are evaluated twice so any side effects will happen twice: Max(rand(), 20000) may evaluate to a number below 20000. You should use an inline function for this or no function at all.
• the argument strings should be defined as const char *.
• the string lengths should use type size_t.

Here is a modified version:

#include <stdlib.h>
#include <string.h>

char *addBinary(const char *a, const char *b) {
    size_t lengthA = strlen(a);
    size_t lengthB = strlen(b);
    size_t new_length = ((lengthA > lengthB) ? lengthA : lengthB) + 1;
    char *result = calloc(new_length + 1, sizeof(char));
    if (result) {
        int carry = 0;
        for (size_t i = new_length; i > 0;) {
            if (idx_a > 0) carry += a[--idx_a] - '0';
            if (idx_b > 0) carry += b[--idx_b] - '0';
            result[--i] = (carry & 1) + '0';
            carry >>= 1;
        }
        if (result[0] == '0' && new_length > 1) {
            // move the digits and null terminator left one position
            memmove(result, result + 1, new_length);
        }
    }
    return result;
}

Answer 3

Let's consider your code step by step.

First of all the function should be declared like

char * addBinary( const char *s1, const char *s2 );

because passed strings are not changed within the function.

Secondly, the function strlen has the return type size_t . You should also use this unsigned ingteger type instead of the signed type int.

Thirdly, in this call of calloc

char *result = calloc( Max(lengthA, lengthB)+2, sizeof(char) );

you are allocating one more byte when it is not required . At first you need to check whether there is an overflow and only in this case to allocate one more byte.

Also in this for loop

    for( int i = Max(lengthA, lengthB); i >= 0; i-- )
    {
        int bit = carry;
        if(idx_a >= 0) bit += a[idx_a--] -'0';
        if(idx_b >= 0) bit += b[idx_b--] -'0';
        carry = bit>>1; 
        result[i] = (bit%2) + '0';
    }

there is a redundant iteration when there is no an overfflow. For example if you have two strings like a = "0", b = "1" then there are two iterations for i equal to 1 and to 0 while you need to add two characters only one time.

Using this return statement

return result+ (result[0] == '0');

is a very bad idea because the function in this case can return a pointer that will not store the address of the allocated memory. In this case you will be unable to free the allocated memory using such a pointer.

And at last if passed strings have leading zeroes then you should ignore them. For example "000000" + "1" should result in "1". This makes the function more flexible and general.

And also always check whether memory was allocated successfully.

Here is a demonstratopn program.

#include <stdio.h>
#include <string.h>

char *addBinary( const char *s1, const char *s2 )
{
    char *s = NULL;

    while ( *s1 == '0' && *( s1 + 1 ) != '\0' ) ++s1;
    while ( *s2 == '0' && *( s2 + 1 ) != '\0' ) ++s2;

    size_t n1 = strlen( s1 );
    size_t n2 = strlen( s2 );

    if (n1 == 0)
    {
        s = malloc( n2 + 1 );
        if (s) strcpy( s, s2 );
    }
    else if (n2 == 0)
    {
        s = malloc( n1 + 1 );
        if (s) strcpy( s, s1 );
    }
    else
    {
        size_t max_n = n1 < n2 ? n2 : n1;

        int carry = 0;

        for (size_t i1 = n1, i2 = n2; ( i1 != 0 && i2 != 0 ) || ( carry && ( i1 != 0 || i2 != 0 ) ); )
        {
            if ( i1 ) carry += s1[--i1] - '0';
            if ( i2 ) carry += s2[--i2] - '0';
            carry >>= 1;
        }

        size_t n = max_n + carry;
        s = calloc( n + 1 , sizeof( char ) );

        if (s != NULL)
        {
            carry = 0;

            for (size_t i = n, i1 = n1, i2 = n2; i != 0; )
            {
                if ( i1 ) carry += s1[--i1] - '0';
                if ( i2 ) carry += s2[--i2] - '0';
                s[--i] = '0' + ( carry & 1 );
                carry >>= 1;
            }
        }
    }

    return s;
}

int main(void) 
{
    const char *s1 = "0";
    const char *s2 = "0";
    
    char *s = addBinary( s1, s2 );

    if ( s ) printf( "\"%s\" + \"%s\" = \"%s\"\n", s1, s2, s );
    
    free( s );

    s1 = "11";
    s2 = "1";
    
    s = addBinary( s1, s2 );
    
    if ( s ) printf( "\"%s\" + \"%s\" = \"%s\"\n", s1, s2, s );
    
    free( s );

    s1 = "1010";
    s2 = "1011";
    
    s = addBinary( s1, s2 );
    
    if ( s ) printf( "\"%s\" + \"%s\" = \"%s\"\n", s1, s2, s );
    
    free( s );

    s1 = "000000";
    s2 = "1";
    
    s = addBinary( s1, s2 );
    
    if ( s ) printf( "\"%s\" + \"%s\" = \"%s\"\n", s1, s2, s );
    
    free( s );

    return 0;
}

Its output is

"0" + "0" = "0"
"11" + "1" = "100"
"1010" + "1011" = "10101"
"000000" + "1" = "1"

By the way it seems that you just copied and pasted the solution found by me here