multiplicación en C sin operadores aritméticos

Question

¿Es posible multiplicar dos números sin usar operadores aritméticos usando C? Usando el operador de desplazamiento a la izquierda, puedo multiplicar cualquier número por 2 solamente. ¿Qué hay de otros números?

Answer 1

void main() 
{ 
    int n1, n2, n3, n4, x, y, i; 
    printf("Enter first number"); 
    scanf("%d", &n1); 
    printf("Enter second number"); 
    scanf("%d", &n2); 
    n3 = n2; 
    n4 = n2; 
    n1-=1; 
    for(i = n1;i > 0;i-=1) 
    { 
    do { 
     x = n2 & n3; 
     y= n2^n3; 
     n2 = x << 1; 
     n3 = y; 
    } while (x); 
    n2 = y; 
    n3 = n4; 
    } 
    printf("product of two number is %d", y); 
    getch(); 
} 

Answer 2

Sí es posible. Puedes hacerlo con operadores lógicos. Después de todo, eso es todo lo que hace el hardware cuando usa un operador aritmético.

Answer 3

Es posible, ver el wiki de una dirección: http://en.wikipedia.org/wiki/Binary_multiplier

Answer 4

Para resolver este problema, lo primero que quiero hacer es encontrar la manera de llegar operaciones aritméticas sencillas utilizando los operadores solo bit a bit.

Por ejemplo, además se puede lograr usando esta técnica

int add(int a, int b) { 
    int c; 
    while (a != 0) { 
     c = b & a; 
     b = b^a; 
     c = c << 1; 
     a = c; 
    } 
    return b; 
} 

Entonces es una cuestión de hacer la multiplicación usando suma:

int mult(int a, int b) { 
    int i = 0; 
    int c = 0; 
    while (i < b) { 
     c = add(c, a); 
     i = add(i, 1); 
    } 
    return c; 
} 

Esta multiplicación aún no funciona si b es negativo, pero como parece un problema de tarea, lo dejo como un ejercicio para ti. ;)

Edit: Si bien la multiplicación es intuitiva una vez que tiene la suma, la función de suma no es tan fácil de entender, por lo que lo explicaré aquí.

Digamos que desea agregar dos números, 11010011 y 10101. La forma habitual de hacerlo es alinearlos así:

11010011 
+ 10101 

Se dará cuenta de que cuando se agregan dos números binarios, si el ith bit de ambos números es 1, entonces el bit resultante es 0, y hay un arrastre a un bit a la izquierda de i.

Este acarreo es lo que almacena la variable 'c' en el código.

//... 
c = b & a; 
//... 
c << 1; 
//... 

Nos poco sabia y B y A para obtener sólo los bits, donde a y b son 1, entonces desplazamiento a la izquierda por 1 para obtener los bits de acarreo.

Luego puede ver los bits donde a y b difieren, es decir, uno de los bits es 1 y el otro bit es 0. El bit resultante en este caso será 1 sin acarreo.

que es lo que esta línea tiendas:

b = b^a; 

La línea anterior esencialmente elimina los bits donde tanto a como b son 1 (ahora se almacenan en C).

Así que ahora tiene otros dos números byc, que debe agregar juntos.

En primer lugar vamos a ver dónde nos encontramos con el ejemplo después de la primera iteración del bucle

c = a = 00100010 
    b = 11000110 

Puede que no sea del todo evidente todavía, pero b está acumulando la suma resultante. A través de más iteraciones del ciclo, más "bits" que se transportan se "vuelven a agregar" a "b", y los acarreos se vuelven a almacenar en "c". En ese sentido, puede pensar en el operador xor como una operación de suma sin acarreo.

Aquí está la segunda iteración del bucle que:

c = a = 00000010 
    b = 11100100 

tercera iteración:

c = a = 00000000 
    b = 11100110 

Ahora c (y) es 0, lo que no hay más equipaje que añadir. Salimos del ciclo y regresamos b. Tenga en cuenta que incluso si continúa el ciclo, ninguno de los números cambiará.