¿La mejor manera de hacer aritmética binaria en C?

Question

estoy aprendiendo C y escribir un programa simple que tomar 2 valores de cadena asumidos a cada ser números binarios y realizar una operación aritmética según la selección del usuario:

• Añadir los dos valores,
• entrada Reste 2 desde la entrada 1, o
• Multiplica los dos valores.

Mi implementación asume que cada carácter en la cadena es un bit binario, p. char bin5 = "0101";, pero parece un enfoque demasiado ingenuo para analizar a través de la cadena un personaje a la vez. Idealmente, me gustaría trabajar directamente con los valores binarios.

¿Cuál es la forma más eficiente de hacer esto en C? ¿Hay una mejor manera de tratar la entrada como valores binarios en lugar de scanf() y obtener cada bit de la cadena?

Hice algunas investigaciones pero no encontré ningún enfoque que fuera obviamente mejor desde la perspectiva de un principiante. ¡Cualquier sugerencia sera apreciada!

Answer 1

Consejo:
No hay mucho que es obviamente mejor que marcha a través de la cadena de un carácter a la vez y asegurándose de que el usuario ha introducido sólo unos y ceros. Tenga en cuenta que, aunque puede escribir realmente rutina de ensamblaje rápido si asume todo es 1 o 0, realmente no desea hacer eso. El usuario puede ingresar cualquier cosa, y le gustaría poder decirles si se equivocaron o no.

Es cierto que esto parece increíblemente lento en comparación con los ciclos de pareja que probablemente lleva agregar los números reales, pero ¿realmente importa si obtiene su respuesta en un nanosegundo o un milisegundo? Los humanos solo pueden detectar 30 milisegundos de latencia de todos modos.

Finalmente, ya lleva mucho más tiempo obtener entradas del usuario y escribir salidas en la pantalla que analizar la cadena o sumar los números, por lo que su algoritmo no es el cuello de botella aquí. Guarde sus optimizaciones de lujo para cosas que en realidad son intensivas desde el punto de vista computacional :-).

Lo que debe centrarse aquí es hacer que la tarea requiera menos mano de obra. Y, resulta que alguien ya hizo eso por ti.

Solución:
Tome un vistazo a the strtol() manpage:

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

Esto le permitirá convertir una cadena (nptr) en cualquier base a un tiempo. También verifica los errores. Ejemplo de uso para la conversión de una cadena binaria:

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

El suministro de base 2 dice strtol para convertir literales binarios.

Answer 2

¿No sería más fácil analizar las cadenas en enteros y luego realizar sus cálculos en los enteros?

Supongo que se trata de una tarea escolar, pero te estoy votando porque pareces estar haciendo un gran esfuerzo.

Answer 3

Primero, te recomiendo que uses cosas como strtol como lo recomienda tgamblin, , es mejor usar las cosas que la lib te da en lugar de crear la rueda una y otra vez.

Pero como estás aprendiendo C hice una pequeña versión sin strtol, , no es ni rápida ni segura, pero jugué un poco con la manipulación de bits como ejemplo.

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

Con el fin de obtener el mejor rendimiento, es necesario distinguir entre la entrada seguros y no seguros a sus funciones.

Por ejemplo, una función como que acepta la entrada del usuario debe ser revisada en busca de caracteres válidos y comprimida para eliminar ceros a la izquierda. En primer lugar, vamos a mostrar un propósito general función de compresión en el lugar:

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

a continuación, proporcionar una función que devuelve corrector sea aprobada en el valor, o NULL si era válido:

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

Entonces la función de entrada en sí:

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

Otras funciones de suma o multiplica debe ser escrito para asumir la entrada ya es válida, ya que habrá sido creado por una de las funciones en º es biblioteca. No voy a proporcionar el código para ellos ya que no es relevante para la cuestión:

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

Si el usuario opta por obtener sus datos de otro lugar que , podría permitir que se llaman checkBinNum() para validarlo.

Si estuviera realmente paranoico, podría verificar cada número que pasa en sus rutinas y actuar en consecuencia (devolver NULO), pero eso requeriría controles relativamente caros que no son necesarios.

Answer 5

Suponiendo que una cadena es un número binario, simplemente porque consiste solo en dígitos del conjunto {0,1} es peligroso. Por ejemplo, cuando su entrada es "11", el usuario puede haber significado once en decimal, no tres en binario. Es este tipo de descuido lo que da lugar a errores horribles. Su entrada es ambiguamente incompleta y realmente debe solicitar que el usuario especifique la base también.