3
\$\begingroup\$

I tried to write a function bin_add() in C to add two positive binary numbers represented as zero terminated strings:

#include <errno.h>
#include <stdbool.h>
#include <stddef.h>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>

#define MAX(x, y) ((x) > (y) ? (x) : (y))

size_t gpp(char const *s)
{
    char *n = strchr(s, '.');
    return n  ? (size_t)(n - s + 1) : 0;
}

char* bin_add(char const *a, char const *b)
{
    char const *inp[] = { a, b };
    size_t ll[] = { strlen(a), strlen(b) };
    size_t pp[] = { gpp(a), gpp(b) };
    size_t OO[2], off[2];

    for (size_t i = 0; i < 2; ++i) {
        OO[i] = pp[i] ? pp[i] - 1 : ll[i];
        pp[i] = pp[i] ? ll[i] - pp[i] : 0;}

    for (size_t i = 0; i < 2; ++i)
        off[i] = OO[i] < OO[!i] ? OO[!i] - OO[i] : 0;

    size_t ML = MAX(OO[0], OO[1]) + MAX(pp[0], pp[1]) + (!!pp[0] || !!pp[1]);
    char *Ol = calloc(ML + 2, 1);
    if(!Ol) return Ol;

    char ops[2];
    int xc = 0;
    size_t lO = ML;
    unsigned cc[2] = { 0 };
    for (size_t i = ML; i; --i) {
        bool pt = false;
        for (size_t l = 0; l < 2; ++l) {
            ops[l] = i <= ll[l] + off[l] && i - off[l] - 1
                       <  ll[l] ? inp[l][i - off[l] - 1] : '0';
            if (ops[l] == '.') {
                if (cc[l]) {
                    free(Ol);
                    return NULL;
                }
                pt = true;
                ++cc[l];
            }
            ops[l] -= '0';
        }
        if (pt) {
            Ol[i] = '.';
            continue;
        }
        if ((Ol[i] = ops[0] + ops[1] + xc) > 1) {
            Ol[i] = 0;
            xc = 1;
        }
        else xc = 0;
        lO = (Ol[i] += '0') == '1' ? i : lO;
    }
    if((Ol[0] = '0' + xc) == '1') return Ol;
        for (size_t i = 0; i <= ML - lO + 1; ++i)
            Ol[i] = Ol[lO + i];

    return Ol;
}

int main(void)
{
    char a[81], b[81];

    while (scanf(" %80[0.1] %80[0.1]", a, b) & 1 << 1) {
        char *c = bin_add(a, b);
        if (!c && errno == ENOMEM) {
            fputs("Not enough memory :(\n\n", stderr);
            return EXIT_FAILURE;
        }
        else if (!c) {
            fputs("Input error :(\n\n", stderr);
            goto clear;
        }

        char* O[] = { a, b, c };
        size_t lO[3], Ol = 0;
        for (size_t i = 0; i < 3; ++i) {
            lO[i] = gpp(O[i]);
            lO[i] = lO[i] ? lO[i] : strlen(i[O]) + 1;
            Ol = lO[i] > Ol ? lO[i] : Ol;
        }

        putchar('\n');
        for (size_t i = 0; i < 3; ++i) {
            for (size_t l = 0; l < Ol - lO[i]; ++l, putchar(' '));
        puts(O[i]);
        }
        putchar('\n');

        free(c);
        clear :{ int c; while ((c = getchar()) != '\n' && c != EOF); }
    }
}

The main() is just included to provide input to the function and pretty-print its results. Every C99 compliant compiler should be able to compile above code.

Do you see any flaws in my code and anything that could be improved?

\$\endgroup\$
2
  • \$\begingroup\$ "A revised version of the code will be posted in an update to this question." Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. \$\endgroup\$ Nov 30, 2018 at 16:12
  • \$\begingroup\$ @SᴀᴍOnᴇᴌᴀ I'll move the reply to an answer. \$\endgroup\$
    – Swordfish
    Nov 30, 2018 at 16:26

2 Answers 2

3
\$\begingroup\$

Do you see any flaws in my code and anything that could be improved?

Segregate code

Splitting into bin_add.c, bin_add.h, main.c would help delineate what is the code, its user interface and test code.

No compilation errors

As posted now, I did not notice any warnings either- good.

Some comments would help

gpp() would benefit with at least a line comment about its goal, expected input, output, etc. Same for bin_add() - which should alert that the return pointer needs to be free'd. This becomes even more important when the user only has access to the declaration in a .h file.

Commenting some of the block of code would help too.

When to shift

When there is not a final carry, code shifts Ol[]. As a final carry with this FP-like code is more rare, I'd shift when there is a carry.

Collapsing

With floating point strings, I expect code to drop trailing zero digits to the right of the '.'.

Leading zero digits are possible based on input. Perhaps eat those too with an early while (*a == '0') a++; and with b. - depends on coding goals though.

Inconsistent bracket style

//                                v ?? 
pp[i] = pp[i] ? ll[i] - pp[i] : 0;}

Hopefully code is auto-formatted.

Inconsistent indentation

if((Ol[0] = '0' + xc) == '1') return Ol;
//  v   Why indented here?
    for (size_t i = 0; i <= ML - lO + 1; ++i)
        Ol[i] = Ol[lO + i];

This implies code is not auto formatted. Save time, and use auto-formatting.

Terse digit like object names lose clarity

The short object names OO, lO, O, Ol, ll look too much like 00, 10, 0, 01, 11. Consider more clear alternatives.

Other examples:
int xc as the carry bit looks more clear as int carry. size_t ML more meaningful as MaxLength.

Input error detection

I'd suggest a separate bool bin_valid(const char *s) and let bin_add() assume valid strings a,b. This would help simplify - a NULL return would only indicate out-of-memory.

Good use of cast to ward off warnings

return n  ? (size_t)(n - s + 1) : 0;
//          ^------^

Misc.

ops[2], cc[2] could be local to for (size_t i = ML; i; --i) {

Good use of const.

Good use of size_t.

Personal preference: Consider char *Ol = calloc(ML + 2, sizeof *Ol);


Main

Do not assume EOF is -1

Simply test if the scanf() result is 2.

// while (scanf(" %80[0.1] %80[0.1]", a, b) & 1 << 1) {
while (scanf(" %80[0.1] %80[0.1]", a, b) == 2) {

ENOMEM

ENOMEM is not part of the standard C.

Test cases

Some specific example test cases would be useful.

maybe even C90/C89

Not quite.

Lots of error: 'for' loop initial declarations are only allowed in C99 or C11 mode problems

warning: control reaches end of non-void function [-Wreturn-type]

error: redefinition of 'i'

\$\endgroup\$
1
  • \$\begingroup\$ I replied to your great review in an answer to the question. \$\endgroup\$
    – Swordfish
    Nov 30, 2018 at 16:28
1
\$\begingroup\$

In reply to @chux review:

Segregate code

Splitting into bin_add.c, bin_add.h, main.c would help delineate what is the code, its user interface and test code.

I understand. Please note that I posted the code contained within one "file" to make copy & paste for testing easier for the readers. I concur, the code should be split up in a header and it's accompanying source file.

Some comments would help

gpp() would benefit with at least a line comment about its goal, expected input, output, etc. Same for bin_add() - which should alert that the return pointer needs to be free'd. This becomes even more important when the user only has access to the declaration in a .h file.

I wrote short specifications of the both functions to go in front of their declaration (prototype) and definition (implementation).

Commenting some of the block of code would help too.

I'd appreciate your input on where coments might be needed on the cleaned up version of the code since I believe in self-documenting code.

When to shift

When there is not a final carry, code shifts Ol[]. As a final carry with this FP-like code is more rare, I'd shift when there is a carry.

Um. Since the code "shifts away" all leading zeros I am not sure your conclusion and suggestion "As a final carry with this FP-like code is more rare, I'd shift when there is a carry" is applicable.

Collapsing

With floating point strings, I expect code to drop trailing zero digits to the right of the '.'.

Yes, that is an oversight of the initial implementation. I'll add code to discard trailing zeros from the result.

Leading zero digits are possible based on input. Perhaps eat those too with an early while (*a == '0') a++; and with b. - depends on coding goals though.

Whith discarding leading zeros at an early stage as you suggest, it is no longer needed to keep track of the last '1' written to the output string. I'll add code to discard leading zeros in the input strings.

Inconsistent bracket style

//                                v ?? 
pp[i] = pp[i] ? ll[i] - pp[i] : 0;}

Hopefully code is auto-formatted.

You are right, that bracket should to to the next line.

Inconsistent indentation

if((Ol[0] = '0' + xc) == '1') return Ol;
//  v   Why indented here?
    for (size_t i = 0; i <= ML - lO + 1; ++i)
        Ol[i] = Ol[lO + i];

This implies code is not auto formatted. Save time, and use auto-formatting.

That was an oversight when posting the question. The original code is properly indented.

Terse digit like object names lose clarity

The short object names OO, lO, O, Ol, ll look too much like 00, 10, 0, 01, 11. Consider more clear alternatives.

Other examples: int xc as the carry bit looks more clear as int carry. size_t ML more meaningful as MaxLength.

I'll think of better names.

Input error detection

I'd suggest a separate bool bin_valid(const char *s) and let bin_add() assume valid strings a, b. This would help simplify - a NULL return would only indicate out-of-memory.

Good point. This will allow to drop counting of radix points from bin_add(). I'll implement a function bool is_valid_binary_string(char const *s).

Misc.

ops[2], cc[2] could be local to for (size_t i = ML; i; --i) {

Right. I changed the point of definition of ops[2]. cc[2] will be dropped as it is no longer needed if the function can rely on valid input.

Personal preference: Consider char *Ol = calloc(ML + 2, sizeof *Ol);

This would help to avoid a pitfall if the code were ever to be changed to work with wide characters. Changed.

Do not assume EOF is -1

Simply test if the scanf() result is 2.

The original code does not assume EOF to be -1. It compares the result of scanf() to 2 just as you suggest, albeit in a rather obfuscated way. I'll change == 1 << 1 to == 2.

ENOMEM

ENOMEM is not part of the standard C.

Since it is no longer needed with bin_add() relying on valid input, I will drop checking errno for ENOMEM.

Also I'll drop the speculation about the code being C89/90 compliant from my post since it contains variable definitions local to for-loops which is not allowed in pre C99 code. Didn't think about that.

A revised version of the code:

#include <stdbool.h>
#include <stddef.h>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>

#define MAX(x, y) ((x) > (y) ? (x) : (y))

/* gpp() (get point position) expects a zero terminated string as input and
   will return the 1-based position of the first occurrence of character '.'
   or 0 if no such character is present in the input string.
*/
size_t gpp(char const *s)
{
    char *n = strchr(s, '.');
    return n ? (size_t)(n - s + 1) : 0;
}

/* Determines if its parameter is a valid binary number consisting only of
   '0' and '1' and containing at most one radix point. The return value is
   true if a valid binary number is passed and false otherwise.
*/
bool is_valid_binary_string(char const *s)
{
    int num_points = 0;
    for (; *s; ++s) {
        if (*s != '1' && *s != '0' && *s != '.')
            return false;
        if (*s == '.' && ++num_points > 1)
            return false;
    }
    return true;
}

/* bin_add() expects two zero terminated strings as input. The both strings
   must not contain other characters than '0' and '1'. Both may contain no or
   one radix point ('.'). The function returns a zero terminated string which
   is the result of the addition of both input strings done in base 2. The
   caller is responsible for deallocating the memory to which a pointer is
   returned. If memory allocation failes the function returns NULL and errno
   is ENOMEM. If one or both input strings do not conform to the expectations
   of the function, it returns NULL.
*/
char* bin_add(char const *a, char const *b)
{
    while (*a == '0') ++a;
    while (*b == '0') ++b;

    char const *input[] = { a, b };
    size_t length[] = { strlen(a), strlen(b) };
    size_t point_position[] = { gpp(a), gpp(b) };
    size_t integer_part[2];
    size_t offset[2];

    for (size_t i = 0; i < 2; ++i) {
        integer_part[i] = point_position[i] ? point_position[i] - 1 : length[i];
        point_position[i] = point_position[i] ? length[i] - point_position[i] : 0;
    }

    for (size_t i = 0; i < 2; ++i)
        offset[i] = integer_part[i] < integer_part[!i]
                  ? integer_part[!i] - integer_part[i]
                  : 0;

    size_t maximum_length = MAX(integer_part[0], integer_part[1]) +
                            MAX(point_position[0], point_position[1]) +
                            (!!point_position[0] || !!point_position[1]);

    char *result = calloc(maximum_length + 2, sizeof(*result));
    if (!result)
        return NULL;

    int carry = 0;
    bool result_contains_point = false;
    for (size_t i = maximum_length; i; --i) {
        char ops[2];
        bool is_radix_point = false;
        for (size_t l = 0; l < 2; ++l) {
            ops[l] = i <= length[l] + offset[l] && i - offset[l] - 1
                < length[l] ? input[l][i - offset[l] - 1] : '0';
            if (ops[l] == '.') {
                result_contains_point = is_radix_point = true;
                break;
            }
            ops[l] -= '0';
        }
        if (is_radix_point) {
            result[i] = '.';
            continue;
        }
        if ((result[i] = ops[0] + ops[1] + carry) > 1) {
            result[i] = 0;
            carry = 1;
        }
        else carry = 0;
        result[i] += '0';
    }

    result[0] = '0' + carry;

    if(result_contains_point)
        while (result[maximum_length] == '0')
            result[maximum_length--] = '\0';

    if (result[0] == '1')
        return result;

    for (size_t i = 0; i <= maximum_length + 1; ++i)
        result[i] = result[i + 1];
    return result;
}

int main(void)
{
    char a[81], b[81];

    while (scanf(" %80[0.1] %80[0.1]", a, b) == 2) {
        if (!is_valid_binary_string(a) || !is_valid_binary_string(b)) {
            fputs("Input error :(\n\n", stderr);
            goto clear;
        }

        char *c = bin_add(a, b);
        if (!c) {
            fputs("Not enough memory :(\n\n", stderr);
            return EXIT_FAILURE;
        }

        char* numbers[] = { a, b, c };
        size_t point_position[3];
        size_t offset = 0;

        for (size_t i = 0; i < 3; ++i) {
            point_position[i] = gpp(numbers[i]);
            point_position[i] = point_position[i] ? point_position[i] : strlen(numbers[i]) + 1;
            offset = point_position[i] > offset ? point_position[i] : offset;
        }

        putchar('\n');
        for (size_t i = 0; i < 3; ++i) {
            for (size_t l = 0; l < offset - point_position[i]; ++l, putchar(' '));
            puts(numbers[i]);
        }
        putchar('\n');

        free(c);

clear:  {   int ch;
            while ((ch = getchar()) != '\n' && ch != EOF);
        }
    }
}
\$\endgroup\$
8
  • \$\begingroup\$ Re: "final carry with this FP-like code is more rare" --> bin_add("101010", "111"), bin_add("0.101010", "111") do not generate a carry. Same magnitude ones do like bin_add("101010", "101010") - and hence more rare. \$\endgroup\$ Nov 30, 2018 at 17:00
  • \$\begingroup\$ @chux I got you, but I really don't feel like rewriting the code based on this. \$\endgroup\$
    – Swordfish
    Nov 30, 2018 at 17:02
  • \$\begingroup\$ is_valid_binary_string("") and is_valid_binary_string(".") return true. I'd expect false - your call. \$\endgroup\$ Nov 30, 2018 at 17:05
  • \$\begingroup\$ Oh i see you have updated. – Yes, didn't want to lose a point to you for that one too ^^ \$\endgroup\$
    – Swordfish
    Nov 30, 2018 at 17:12
  • \$\begingroup\$ "" and "." are both considered "0"` by bin_add() so they are valid as far as bin_add() is concerned. \$\endgroup\$
    – Swordfish
    Nov 30, 2018 at 17:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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