Лучший способ сделать двоичную арифметику в C? - PullRequest
8 голосов
/ 23 марта 2009

Я изучаю C и пишу простую программу, которая будет принимать 2 строковых значения, каждое из которых должно быть двоичным числом, и выполнять арифметическую операцию в соответствии с выбором пользователя:

  • Добавьте два значения,
  • Вычтите вход 2 из входа 1 или
  • Умножьте два значения.

Моя реализация предполагает, что каждый символ в строке является двоичным битом, например char bin5 = "0101";, но кажется слишком наивным подход к анализу строки по символу за раз. В идеале я бы хотел работать с двоичными значениями напрямую.

Какой самый эффективный способ сделать это в C? Есть ли лучший способ обрабатывать ввод как двоичные значения, а не scanf() и получать каждый бит из строки?

Я провел какое-то исследование, но не нашел ни одного подхода, который был бы явно лучше с точки зрения начинающего. Любые предложения будут оценены!

Ответы [ 5 ]

12 голосов
/ 23 марта 2009

Совет:
Нет ничего лучше, чем проходить по строке символ за раз и убедиться, что пользователь вводит только единицы и нули. Имейте в виду, что даже если вы могли бы написать действительно подпрограмму быстрой сборки, если вы предполагаете, все равно 1 или 0, вы на самом деле не хотите этого делать. Пользователь может ввести что угодно, и вы хотели бы сказать им, если они облажались или нет.

Это правда, что это кажется ошеломляюще медленным по сравнению с парными циклами, которые, вероятно, требуются для сложения фактических чисел, но действительно ли имеет значение, получите ли вы свой ответ за наносекунду или миллисекунду? В любом случае, люди могут обнаружить только 30 миллисекунд задержки.

Наконец, для получения ввода от пользователя и записи вывода на экран уже требуется гораздо больше времени, чем для анализа строки или добавления чисел, поэтому ваш алгоритм вряд ли является здесь узким местом. Сохраните свои причудливые оптимизации для вещей, которые на самом деле требуют больших вычислительных ресурсов: -).

На чем вы должны сосредоточиться, это делает задачу менее трудоемкой. И, оказывается, кто-то уже сделал это для вас.

Решение:
Взгляните на справочную страницу strtol() :

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

Это позволит вам преобразовать строку (nptr) в любой базе в long. Он также проверяет ошибки. Пример использования для преобразования двоичной строки:

#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.
}

Предоставление базы 2 говорит strtol преобразовать двоичные литералы.

3 голосов
/ 23 марта 2009

Прежде всего, я рекомендую использовать такие вещи, как strtol, как рекомендует tgamblin, лучше использовать то, что дает вам библиотека, а не создавать колесо снова и снова.

Но так как вы изучаете C, я сделал небольшую версию без strtol, это не быстро и не безопасно, но я немного поиграл с манипулированием битами в качестве примера.

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;
}
1 голос
/ 23 марта 2009

Чтобы добиться максимальной производительности, вам необходимо различать доверенный и ненадежный ввод ваших функций.

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

// 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");
}

Затем предоставьте функцию проверки, которая возвращает либо переданное значение, либо NULL, если оно недопустимо:

// 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;
}

Тогда сама функция ввода:

#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;
}

Другие функции для добавления или умножения должны быть написаны так, чтобы предполагать, что ввод уже действителен, поскольку он будет создан одной из функций в этой библиотеке. Я не буду предоставлять им код, поскольку он не имеет отношения к вопросу:

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

Если пользователь выбирает источник своих данных откуда-то, кроме getBinNum(), вы можете позволить ему вызвать checkBinNum() для проверки.

Если бы вы были действительно параноиком, вы могли бы проверить каждый номер, переданный вашей подпрограмме, и действовать соответствующим образом (вернуть NULL), но для этого потребуются относительно дорогие проверки, которые не нужны.

0 голосов
/ 27 ноября 2010

Предполагать, что строка является двоичным числом просто потому, что оно состоит только из цифр из набора {0,1}, опасно. Например, когда вы вводите «11», пользователь может иметь в виду одиннадцать в десятичном виде, а не три в двоичном. Именно такая неосторожность порождает ужасные ошибки. Ваш ввод неоднозначно неполный, и вы должны действительно запросить, чтобы пользователь также указал базу.

0 голосов
/ 23 марта 2009

Не проще ли разобрать строки в целые числа, а затем выполнить математические вычисления над целыми числами?

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

...