Converting negative decimal to two's complement in C

Question

I'm writing a program that, assuming the input is always a valid negative decimal integer, returns the two's complement binary representation (16 bit).

My logic here is that I take in inputs from the command line, and convert that with a simple conversion to binary and add them to the initialized binary array. Then, I take the one's complement (just change 0's to 1's and vise versa) and put that in the onesCom array. However, for the adding 1 part to find the two's complement, I think this is where the issue is but I'm struggling to find it. I am performing binary addition to the least significant bit.

Answer 1

As your snippet is completely blurred, I can only suggest you two approaches to the problem:

• The first assuming you are doing two's complement arithmethic all the time, in which case the digit adding must be done with sign.
• The second assuming you only parse unsigned values and retaining the sign to make the sign exchange at the end.

Probably both approaches will lead to almost the same efficiency and be compiled into very similar code. I have no preference for any of them.

int decode(char *str, int base)
{
    int result = 0,
        c,
        neg = FALSE;

    /* skip whitespace, delete this if you don't
     * want to cope with whitespace */
    for (; isspace(c = *str); str++) {
        continue;
    }

    if (*str == '-') {
        neg = TRUE; /* negative */
        str++; /* skip it */
    }

    /* the next characters might be all digits */
    for (; isdigit(c = *str); str++) {

        /* multiply by the base */
        result *= base;

        /* add positive for positives and
         * subtract it for negatives */
        int d = c - '0'; /* convert c to the digit value */

        /* negative if number is negative */
        if (neg) d = -d;

        /* and add/subtract it */
        result = result + d;
    }

    /* :) got it!! */
    return result;
}

and the second approach is:

int decode(char *str, int base)
{
    int result = 0,
        c,
        neg = FALSE;

    /* skip whitespace, delete this if you don't
     * want to cope with whitespace */
    for (; isspace(c = *str); str++) {
        continue;
    }

    if (*str == '-') {
        neg = TRUE; /* negative */
        str++; /* skip it */
    }

    /* the next characters might be all digits */
    for (; isdigit(c = *str); str++) {

        /* multiply by the base */
        result *= base;

        /* add positive for positives and
         * subtract it for negatives */
        int d = c - '0'; /* convert c to the digit value */

        /* and add/subtract it */
        result = result + d;
    }

    /* :) got it!! */
    return neg ? -result : result;
}

Can you see the differences? (hint, I have eliminated one line in the loop and changed one line at the end :) )

If you want to run this code in a full, complete and verifiable example, there's one below, just put one of the above functions in place of the other, and run it.

#include <stdio.h>
#include <ctype.h>

/* these macros are for easy printing, and outputting the file, line and
 * function name where the trace is being made */
#define F(_f) __FILE__":%d:%s:"_f, __LINE__, __func__
#define P(_f, ...) printf(F(_f), ##__VA_ARGS__)

/* I use these for portability, as <stdbool.h> is not always available */
#define FALSE       (0)
#define TRUE        (!FALSE)

int decode(char *str, int base)
{
    /* substitute here the body of the function above you want to test */
}

int main()
{
    static char *tests[] = {
        "0", "-1", "-210", "-211", "-222", "1",
        "210", "211", "222", "5400",
        /* add more testing cases to your wish */
        NULL,
    };

    int i, passed = 0;
    for (i = 0; tests[i]; i++) {

        char *test = tests[i];
        int expected, actual;

        P("Testing '%s' conversion\n", test);

        /* expected, decoded with system routines */
        if (sscanf(test, "%i", &expected) != 1) {
            P("problem scanning %s\n", test);
            continue;
        }

        /* actual, decoded with our function */
        actual = decode(test, 10);
        char *operator = actual == expected ? "==" : "!=";
        P("Test result: actual(%i) %s expected(%i)\n",
                actual, operator, expected);
        if (actual == expected)
            passed++;
    }
    P("passed %d/%d tests\n", passed, i);
}

Edit

The following code will allow you to easily convert your value to binary:

#define CHK(_n) ((_n) <= sz)

char *to_binary(int p_val, char *buf, size_t sz)
{
    CHK(2); /* at least two bytes of buffer space */
    buf += sz; /* we start from the end, backwards to avoid having to use
                * one bit masks moving all the time around */
    *--buf = '\0'; /* this is the last '\0' that should end the string */
    sz--; /* update buffer size */

    /* we operate better with unsigned, as the
     * sign doesn't get involved in shifts (we are reinterpreting
     * the sign bit as a normal bit, which makes the assumption that
     * integers are stored in two's complement.  This is essentially
     * nonportable code, but it will work in the stated assumptions. */
    unsigned val = (unsigned) p_val;

    /* the first below is the second char we check
     * above */
    do {
        *--buf = val & 1 ? '1' : '0';
        sz--;
        val >>= 1;
    } while (CHK(1) && val);
    return buf; /* return what we have */
}

And the final main() code looks like this:

int main()
{
    static char *tests[] = {
        "0", "-1", "-210", "-211", "-222", "1",
        "210", "211", "222", "5400",
        NULL,
    };

    int i, passed = 0;
    for (i = 0; tests[i]; i++) {

        char *test = tests[i];
        int expected, actual;

        P("Testing '%s' conversion\n", test);

        /* expected, decoded with system routines */
        if (sscanf(test, "%i", &expected) != 1) {
            P("problem scanning %s\n", test);
            continue;
        }

        /* actual, decoded with our function */
        actual = decode(test, 10);
        char *operator = actual == expected ? "==" : "!=";
        char buff[100]; /* temporary variable to hold the
                         * converted value to binary */
        P("Test result: actual(%i/0b%s)\n",
                actual,
                to_binary(actual, buff, sizeof buff));
        P("        %s expected(%i/0b%s)\n",
                operator,
                expected,
                to_binary(expected, buff, sizeof buff));
        if (actual == expected)
            passed++;
    }
    P("passed %d/%d tests\n", passed, i);
}

Answer 2

When converting from one-complement to two-complement, i.e. adding 1, your loop should start from the LSB, not from the MSB.

Therefore,

                        for (j=15; j>=0; j--) { // <-- Error Here
                                if (onesCom[j] == 1 && carryOver == 1) {
                                        twosCom[j] = 0;
                                } else if (onesCom[j] == 0 && carryOver == 1) {
                                        twosCom[j] = 1;
                                        carryOver = 0;
                                } else {
                                        twosCom[j] = onesCom[j];
                                }
                           }

Should be replaced by:

                        for (j=0; j<=15; j++) {
                                if (onesCom[j] == 1 && carryOver == 1) {
                                        twosCom[j] = 0;
                                } else if (onesCom[j] == 0 && carryOver == 1) {
                                        twosCom[j] = 1;
                                        carryOver = 0;
                                } else {
                                        twosCom[j] = onesCom[j];
                                }
                        }

In your code, you calculate the one-complement then deduce the two-complement. Please note that it is easier to directly calculate the two-complement, in case you don't need the one-complement, like this:

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

int main(int argc, char *argv[]) {
    int binary[16] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
    if (argc == 1) return 1;
    int decimal = atoi(argv[1]);
    int counter = 0;
    if (decimal > -32768 && decimal < 0) {
        decimal = 65536 + decimal;
        while(decimal > 0) {
                binary[counter] = decimal%2;
                decimal = decimal/2;
                counter++;
        }
        for (int length = 15; length >=0; length--) {
                printf("%d", binary[length]);
        }
        printf ("\n");
    } 
    return 0;
}