Best way to do binary arithmetic in C?

Question

I am learning C and am trying to write a program that will take 2 value from a user and will check if these strings are binary values (composed of the characters 1 or 0 is how I approached it) before attempting to, according to user selection:

• Add the two values,
• Subtract input 2 from input 1, or
• Multiply the two values.

I can implement the functions to do the math when I assume each character in the string is a binary bit in the manner of char string1 = "0101";, but it does seem a little silly to parse through the string a character at a time to do this kind of math (assembly would be much faster).

I am wondering what the most efficient way to do this sort of thing would be in C? I am also wondering if there would be a better way to deal with the user input than to scanf() into a string and continue to use the data as a string after you've checked if the contents are numeric values of 1 or 0?

I did look around stackoverflow.com and did some web searches, but I didn't find anything that seemed obviously better to a C beginner such as myself. Any tips or suggestions would be appreciated, since I am trying to learn to be efficient in my code from early on.

Answer 1

Wouldn't it be easier to parse the strings into integers, and then perform your maths on the integers?

I'm assuming this is a school assignment, but i'm upvoting you because you appear to be giving it a good effort.

Answer 2

Advice:
There's not much that's obviously better than marching through the string a character at a time and making sure the user entered only ones and zeros. Keep in mind that even though you could write a really fast assembly routine if you assume everything is 1 or 0, you don't really want to do that. The user could enter anything, and you'd like to be able to tell them if they screwed up or not.

It's true that this seems mind-bogglingly slow compared to the couple cycles it probably takes to add the actual numbers, but does it really matter if you get your answer in a nanosecond or a millisecond? Humans can only detect 30 milliseconds of latency anyway.

Finally, it already takes far longer to get input from the user and write output to the screen than it does to parse the string or add the numbers, so your algorithm is hardly the bottleneck here. Save your fancy optimizations for things that are actually computationally intensive :-).

What you should focus on here is making the task less manpower-intensive. And, it turns out someone already did that for you.

Solution:
Take a look at the strtol() manpage:

long strtol(const char *nptr, char **endptr, int base);

This will let you convert a string (nptr) in any base to a long. It checks errors, too. Sample usage for converting a binary string:

#include <stdlib.h>

char buf[MAX_BUF];
get_some_input(buf);

char *err;
long number = strtol(buf, &err, 2);
if (*err) {
    // bad input: try again?
} else {
    // number is now a long converted from a valid binary string.
}

Supplying base 2 tells strtol to convert binary literals.

Answer 3

First out I do recommend that you use stuff like strtol as recommended by tgamblin, it's better to use things that the lib gives to you instead of creating the wheel over and over again.

But since you are learning C I did a little version without strtol, it's neither fast or safe but I did play a little with the bit manipulation as a example.

int main()
{
    unsigned int data = 0;
    int i = 0;

    char str[] = "1001";

    char* pos;
    pos = &str[strlen(str)-1];

    while(*pos == '0' || *pos == '1')
    {
        (*pos) -= '0';
        data += (*pos) << i;

        i++;
        pos--;
    }

    printf("data %d\n", data);
    return 0;
}

Answer 4

In order to get the best performance, you need to distinguish between trusted and untrusted input to your functions.

For example, a function like getBinNum() which accepts input from the user should be checked for valid characters and compressed to remove leading zeroes. First, we'll show a general purpose in-place compression function:

// General purpose compression removes leading zeroes.
void compBinNum (char *num) {
    char *src, *dst;

    // Find first non-'0' and move chars if there are leading '0' chars.
    for (src = dst = num; *src == '0'; src++);
    if (src != dst) {
        while (*src != '\0')
            *dst++ = *src++;
        *dst = '\0';
    }

    // Make zero if we removed the last zero.
    if (*num == '\0')
            strcpy (num, "0");
}

Then provide a checker function that returns either the passed in value, or NULL if it was invalid:

// Check untested number, return NULL if bad.
char *checkBinNum (char *num) {
    char *ptr;

    // Check for valid number.
    for (ptr = num; *ptr == '0'; ptr++)
        if ((*ptr != '1') && (*ptr != '0'))
            return NULL;

    return num;
}

Then the input function itself:

#define MAXBIN 256

// Get number from (untrusted) user, return NULL if bad.
char *getBinNum (char *prompt) {
    char *num, *ptr;

    // Allocate space for the number.
    if ((num = malloc (MAXBIN)) == NULL)
        return NULL;

    // Get the number from the user.
    printf ("%s: ", prompt);
    if (fgets (num, MAXBIN, stdin) == NULL) {
        free (num);
        return NULL;
    }

    // Remove newline if there.
    if (num[strlen (num) - 1] == '\n')
        num[strlen (num) - 1] = '\0';

    // Check for valid number then compress.
    if (checkBinNum (num) == NULL) {
        free (num);
        return NULL;
    }
    compBinNum (num);

    return num;
}

Other functions to add or multiply should be written to assume the input is already valid since it will have been created by one of the functions in this library. I won't provide the code for them since it's not relevant to the question:

char *addBinNum (char *num1, char *num2) {...}
char *mulBinNum (char *num1, char *num2) {...}

If the user chooses to source their data from somewhere other than getBinNum(), you could allow them to call checkBinNum() to validate it.

If you were really paranoid, you could check every number passed in to your routines and act accordingly (return NULL), but that would require relatively expensive checks that aren't necessary.