Неверный результат при добавлении двоичных строк

Question

Я получаю неверный результат при добавлении двух двоичных строк "11" + "11". Я ожидаю «110», но я получаю ответ «010». Я добавил особый случай, если керри все еще равен 1.

char *addBinary(char *str1, char *str2)
{
    int len1 = strlen(str1); //assume both string lengths are same
    char *res = (char *)malloc((len1 + 1) * sizeof(char));
    int i, a, b;
    int carry = 0;
    char result;
    for (i = len1 - 1; i >= 0; i--)
    {
        a = str1[i] - '0';
        b = str2[i] - '0';
        carry = a + b + carry;
        printf("%d %d %d \n", a, b, carry % 2);
        result = carry % 2 + '0'; //convert to character
        carry = carry / 2;
        str1[i] = result; //use the existing string for the result
    }
    if (carry == 0)
    { //if there is no carry just use the existing string and return
        printf("Final without carry %s \n", str1);
        return str1;
    }
    else
    { //there was a carry, so put 1 in the 0th location and copy the string
        res[0] = 1;
        memcpy(res + 1, str1, sizeof(char) * len1);
        printf("Final %s %s %d\n", res, str1,strlen(res));
        return res;
    }
}

int main()
{
    char bin_str1[] = "11";
    char bin_str2[] = "11";
    printf("%s \n",addBinary(bin_str1, bin_str2));
    return 0;
}

Answer 1

Еще одна вещь, о которой следует подумать: если у вас есть что-то вроде этого:

char bin_str1[] = "10";
char bin_str2[] = "11";

Ваша addBinary() функция не возвращает res, но str1.

Теперь вот смысл: если вы назначите указатель на вашу функцию, чтобы вы могли освободить память обратно в Систему, у вас будет неверный free().

Один из подходов может быть таким:

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

char *addBinary(char *str1, char *str2);

int main( void )
{
    char bin_str1[] = "11";
    char bin_str2[] = "11";
    char *ptr = addBinary( bin_str1, bin_str2 );

    if ( ptr )
    {
        printf("%s \n",ptr );
        free( ptr );
    }
}

char *addBinary(char *str1, char *str2)
{
    char *res = calloc( strlen( str1 ) + strlen( str2 ), sizeof( *res ) );
    int a, b, carry = 0;
    size_t i = strlen( str1 ) - 1;

    while ( i > 0 )
    {
        a = str1[i] - '0';
        b = str2[i] - '0';
        carry += a + b;
        printf("%d %d %d \n", a, b,( carry % 2));
        str1[i] = (char)( carry % 2 + '0'); ///convert to character
        carry = carry / 2;
        i--;
    }
    if ( carry == 0 )
    { ///if there is no carry RETURN NULL
        printf("Final without carry %s \n", str1);
        free( res );
        return NULL;
    }
    else
    { //there was a carry, so put 1 in the 0th location and copy the string
        res[0] = '1';
        strcat( res, str1 );
        printf("Final %s %s %zu\n", res, str1,strlen( res ));
        return res;
    }
}

Или вы можете сбросить malloc и использовать его так:

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

int addBinary( char *dest, char *const str1, const char *const str2);

int main( void )
{
    char bin_str1[] = "11";
    char bin_str2[] = "11";
    char dest[256] = { 0 };

    if ( addBinary( dest, bin_str1, bin_str2 ) )
    {
        printf("Dest = %s\n", dest );
    }
}

int addBinary( char *dest, char *const str1, const char *const str2)
{
    int a, b, carry = 0;
    size_t i = strlen( str1 ) - 1;

    while ( i > 0 )
    {
        a = str1[i] - '0';
        b = str2[i] - '0';
        carry += a + b;
        str1[i] = (char)( carry % 2 + '0'); ///convert to character
        carry = carry / 2;
        i--;
    }
    if ( carry )
    {
        dest[0] = '1';
        strcat( dest, str1 );
        return 1;
    }
    return 0;
}

Я внес некоторые изменения в ваш код, чтобы уменьшить его для лучшего чтения.

Answer 2

У вас есть две основные проблемы:

Сначала при выделении места для res:

char *res = (char *)malloc((len1 + 1) * sizeof(char));

Вам необходимо выделить место для len1+2 (перенос и NUL завершение), в противном случае ваш memcpy будет писать вне границ (вам следует скопировать len1+1 элементы, в противном случае не гарантируется, что res NUL прекращено). Также обратите внимание, что в случае, если вы возвращаете str1, память просочилась.

Вторая проблема возникает, когда вы устанавливаете первый символ в res, который вы устанавливаете в качестве печатного символа:

res[0] = 1;

Вместо этого вы должны установить '1'.