relacionales - operadores logicos en dev c++

¿Es así como se implementa el operador+en C?

Question

Al comprender cómo se implementan los operadores primitivos como + , - , * y / en C, encontré el siguiente fragmento de una respuesta interesante .

// replaces the + operator
int add(int x, int y) {
while(x) {
int t = (x & y) <<1;
y ^= x;
x = t;
}
return y;
}

Parece que esta función demuestra cómo + funciona realmente en segundo plano. Sin embargo, es demasiado confuso para mí entenderlo. ¡Creí que tales operaciones se realizan utilizando directivas de ensamblaje generadas por el compilador durante mucho tiempo!

¿El operador + implementa como el código publicado en la mayoría de las implementaciones? ¿Aprovecha esto el complemento a dos u otras características dependientes de la implementación?

Answer 1

Mi pregunta es: ¿el operador + se implementa como el código publicado en la mayoría de las implementaciones?

Respondamos la pregunta real. El compilador implementa todos los operadores como una estructura de datos interna que finalmente se traduce en código después de algunas transformaciones. No puede decir qué código se generará con una sola adición porque casi ningún compilador del mundo real genera código para declaraciones individuales.

El compilador es libre de generar cualquier código siempre que se comporte como si las operaciones reales se realizaran de acuerdo con el estándar. Pero lo que sucede realmente puede ser algo completamente diferente.

Un simple ejemplo:

static int
foo(int a, int b)
{
return a + b;
}
[...]
int a = foo(1, 17);
int b = foo(x, x);
some_other_function(a, b);

No es necesario generar instrucciones de adición aquí. Es perfectamente legal que el compilador traduzca esto a:

some_other_function(18, x * 2);

O tal vez el compilador se da cuenta de que llama a la función foo varias veces seguidas y que es una aritmética simple y generará instrucciones vectoriales para ella. O que el resultado de la adición se use para la indexación de matrices más tarde y se usará la instrucción lea .

Simplemente no puede hablar sobre cómo se implementa un operador porque casi nunca se usa solo.

Answer 2

Parece que esta función demuestra cómo + funciona realmente en segundo plano

No. Esto se traduce a la instrucción nativa de add máquina, que en realidad está utilizando el sumador de hardware, en la ALU .

Si se pregunta cómo agrega la computadora, aquí hay un sumador básico.

Todo en la computadora se hace usando puertas lógicas, que están hechas principalmente de transistores. El sumador completo tiene medios sumadores.

Para un tutorial básico sobre puertas lógicas y sumadores, vea this . El video es extremadamente útil, aunque largo.

En ese video, se muestra un medio sumador básico. Si quieres una breve descripción, esta es:

El medio sumador suma dos bits dados. Las combinaciones posibles son:

• Agregar 0 y 0 = 0
• Suma 1 y 0 = 1
• Suma 1 y 1 = 10 (binario)

Entonces, ¿cómo funciona el medio sumador? Bueno, está compuesto por tres puertas lógicas, la and , xor y la nand . El nand da una corriente positiva si ambas entradas son negativas, lo que significa que esto resuelve el caso de 0 y 0. El xor da una salida positiva, una de las entradas es positiva y la otra negativa, lo que significa que resuelve el problema de 1 y 0. El and da una salida positiva solo si ambas entradas son positivas, de modo que resuelve el problema de 1 y 1. Entonces, básicamente, ahora tenemos nuestro medio sumador. Pero todavía solo podemos agregar bits.

Ahora hacemos nuestro sumador completo. Un sumador completo consiste en llamar al medio sumador una y otra vez. Ahora esto tiene un acarreo. Cuando sumamos 1 y 1, obtenemos un carry 1. Entonces, lo que hace el sumador completo es, toma el carry del medio sumador, lo almacena y lo pasa como otro argumento al medio sumador.

Si está confundido, ¿cómo puede pasar el carry? Básicamente, primero agrega los bits con el medio sumador y luego agrega la suma y el carry. Así que ahora has agregado el carry, con los dos bits. Entonces haces esto una y otra vez, hasta que los bits que tienes que agregar hayan terminado, y luego obtengas tu resultado.

¿Sorprendido? Así es como sucede realmente. Parece un proceso largo, pero la computadora lo hace en fracciones de nanosegundo, o para ser más específicos, en medio ciclo de reloj. A veces se realiza incluso en un solo ciclo de reloj. Básicamente, la computadora tiene la ALU (una parte importante de la CPU ), memoria, buses, etc.

Si desea aprender hardware de la computadora, desde puertas lógicas, memoria y ALU, y simular una computadora, puede ver este curso, del cual aprendí todo esto: construir una computadora moderna desde los primeros principios

Es gratis si no desea un certificado electrónico. La segunda parte del curso llegará en primavera este año.

Answer 3

C usa una máquina abstracta para describir lo que hace el código C. Entonces, cómo funciona no está especificado. Hay "compiladores" de C que realmente compilan C en un lenguaje de script, por ejemplo.

Pero, en la mayoría de las implementaciones de C, + entre dos enteros más pequeños que el tamaño entero de la máquina se traducirá en una instrucción de ensamblaje (después de muchos pasos). Las instrucciones de ensamblaje serán traducidas al código de la máquina e integradas en su ejecutable. Assembly es un lenguaje "un paso eliminado" del código de máquina, destinado a ser más fácil de leer que un montón de binarios empaquetados.

Ese código de máquina (después de muchos pasos) es interpretado por la plataforma de hardware de destino, donde es interpretado por el decodificador de instrucciones en la CPU. Este decodificador de instrucciones toma la instrucción y la traduce en señales para enviar a lo largo de "líneas de control". Estas señales enrutan los datos de los registros y la memoria a través de la CPU, donde los valores se suman a menudo en una unidad lógica aritmética.

La unidad de lógica aritmética podría tener sumadores y multiplicadores separados, o podría mezclarlos.

La unidad de lógica aritmética tiene un grupo de transistores que realizan la operación de suma y luego producen la salida. Dicha salida se enruta a través de las señales generadas desde el decodificador de instrucciones, y se almacena en la memoria o registros.

El diseño de dichos transistores tanto en la unidad de lógica aritmética como en el decodificador de instrucciones (así como las partes que he pasado por alto) está grabado en el chip de la planta. El patrón de grabado a menudo se produce compilando un lenguaje de descripción de hardware, que toma una abstracción de lo que está conectado a qué y cómo funcionan y genera transistores y líneas de interconexión.

El lenguaje de descripción de hardware puede contener cambios y bucles que no describen cosas que suceden en el tiempo (como una tras otra) sino más bien en el espacio : describe las conexiones entre diferentes partes del hardware. Dicho código puede parecerse muy vagamente al código que publicó anteriormente.

Lo anterior pasa por alto muchas partes y capas y contiene imprecisiones. Esto se debe a mi propia incompetencia (he escrito hardware y compiladores, pero no soy experto en ninguno) y porque todos los detalles requerirían una carrera o dos, y no una publicación SO.

Here hay una publicación SO sobre un sumador de 8 bits. Here hay una publicación que no es SO, donde notarás que algunos de los sumadores solo usan operator+ en el HDL! (El HDL mismo comprende + y genera el código de sumador de nivel inferior para usted).

Answer 4

Casi cualquier procesador moderno que pueda ejecutar código C compilado tendrá soporte incorporado para la adición de enteros. El código que publicó es una forma inteligente de realizar la suma de enteros sin ejecutar un código de operación de suma de enteros, pero no es cómo se realiza normalmente la suma de enteros. De hecho, el enlace de función probablemente usa alguna forma de suma de enteros para ajustar el puntero de la pila.

El código que publicó se basa en la observación de que al agregar x e y, puede descomponerlo en los bits que tienen en común y los bits que son exclusivos de uno de x o y.

La expresión x & y (bitwise AND) da los bits comunes a x e y. La expresión x ^ y (OR exclusivo bit a bit) da los bits que son únicos para uno de x o y.

La suma x + y puede reescribirse como la suma de dos veces los bits que tienen en común (ya que tanto x como y contribuyen con esos bits) más los bits que son únicos para x o y.

(x & y) << 1 es el doble de los bits que tienen en común (el desplazamiento a la izquierda por 1 efectivamente se multiplica por dos).

x ^ y son los bits que son exclusivos de uno de x o y.

Entonces, si reemplazamos x por el primer valor e y por el segundo, la suma no debería modificarse. Puede pensar en el primer valor como el acarreo de las adiciones bit a bit, y el segundo como el bit de orden inferior de las adiciones bit a bit.

Este proceso continúa hasta que x es cero, momento en el que y retiene la suma.

Answer 5

Cuando agrega dos bits, el resultado es el siguiente: (tabla de verdad)

a | b | sum (a^b) | carry bit (a&b) (goes to next)
--+---+-----------+--------------------------------
0 | 0 | 0 | 0
0 | 1 | 1 | 0
1 | 0 | 1 | 0
1 | 1 | 0 | 1

Entonces, si haces xor bit a bit, puedes obtener la suma sin llevar. Y si lo haces bit a bit y puedes obtener los bits de acarreo.

Extender esta observación para los números multibit a y b

a+b = sum_without_carry(a, b) + carry_bits(a, b) shifted by 1 bit left
= a^b + ((a&b) << 1)

Una vez que b es 0 :

a+0 = a

Entonces el algoritmo se reduce a:

Add(a, b)
if b == 0
return a;
else
carry_bits = a & b;
sum_bits = a ^ b;
return Add(sum_bits, carry_bits << 1);

Si se deshace de la recursividad y la convierte en un bucle

Add(a, b)
while(b != 0) {
carry_bits = a & b;
sum_bits = a ^ b;
a = sum_bits;
b = carrry_bits << 1; // In next loop, add carry bits to a
}
return a;

Con el algoritmo anterior en mente, la explicación del código debería ser más simple:

int t = (x & y) << 1;

Llevar pedazos. El bit de transporte es 1 si 1 bit a la derecha en ambos operandos es 1.

y ^= x; // x is used now

Adición sin acarreo (bits de transporte ignorados)

x = t;

Reutilice x para configurarlo para llevar

while(x)

Repita mientras haya más bits de acarreo

Una implementación recursiva (más fácil de entender) sería:

int add(int x, int y) {
return (y == 0) ? x : add(x ^ y, (x&y) << 1);
}

Parece que esta función demuestra cómo + funciona realmente en segundo plano

No. Usualmente (casi siempre) la suma de enteros se traduce en la instrucción de máquina add. Esto solo demuestra una implementación alternativa usando bitor xor y y.

Answer 6

El código que encontró intenta explicar cómo un hardware informático muy primitivo podría implementar una instrucción "agregar". Digo "podría" porque puedo garantizar que este método no es utilizado por ninguna CPU, y explicaré por qué.

En la vida normal, utiliza números decimales y ha aprendido cómo sumarlos: para sumar dos números, sume los dos dígitos más bajos. Si el resultado es inferior a 10, anote el resultado y proceda a la siguiente posición de dígitos. Si el resultado es 10 o más, anote el resultado menos 10, pase al siguiente dígito, compre y recuerde agregar 1 más. Por ejemplo: 23 + 37, agrega 3 + 7 = 10, escribe 0 y recuerda agregar 1 más para la siguiente posición. En la posición 10s, sumas (2 + 3) + 1 = 6 y anotas eso. El resultado es 60.

Puedes hacer exactamente lo mismo con números binarios. La diferencia es que los únicos dígitos son 0 y 1, por lo que las únicas sumas posibles son 0, 1, 2. Para un número de 32 bits, manejaría una posición de un dígito después del otro. Y así es como lo haría realmente un hardware informático primitivo.

Este código funciona de manera diferente. Usted sabe que la suma de dos dígitos binarios es 2 si ambos dígitos son 1. Entonces, si ambos dígitos son 1, entonces agregaría 1 más en la siguiente posición binaria y escribiría 0. Eso es lo que hace el cálculo de t: encuentra todos los lugares donde ambos dígitos binarios son 1 (ese es el &) y los mueve a la siguiente posición de dígitos (<< 1). Luego hace la suma: 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, 1 + 1 es 2, pero escribimos 0. Eso es lo que hace el operador o el excluyente.

Pero no se han manejado todos los 1 que tenía que manejar en la siguiente posición de dígito. Todavía necesitan ser agregados. Es por eso que el código hace un bucle: en la siguiente iteración, se agregan todos los 1 adicionales.

¿Por qué ningún procesador lo hace así? Porque es un bucle, y a los procesadores no les gustan los bucles, y es lento. Es lento, porque en el peor de los casos, se necesitan 32 iteraciones: si agrega 1 al número 0xffffffff (32 1 bits), la primera iteración borra el bit 0 de y y establece x a 2. La segunda iteración borra el bit 1 de y y establece x a 4. Y así sucesivamente. Se necesitan 32 iteraciones para obtener el resultado. Sin embargo, cada iteración tiene que procesar todos los bits de x e y, lo que requiere mucho hardware.

Un procesador primitivo haría las cosas con la misma rapidez que la aritmética decimal, desde la posición más baja hasta la más alta. También requiere 32 pasos, pero cada paso procesa solo dos bits más un valor desde la posición de bit anterior, por lo que es mucho más fácil de implementar. E incluso en una computadora primitiva, uno puede permitirse hacer esto sin tener que implementar bucles.

Una CPU moderna, rápida y compleja utilizará un "sumador de suma condicional". Especialmente si el número de bits es alto, por ejemplo, un sumador de 64 bits, ahorra mucho tiempo.

Un sumador de 64 bits consta de dos partes: primero, un sumador de 32 bits para el más bajo de 32 bits. Ese sumador de 32 bits produce una suma y un "carry" (un indicador de que se debe agregar un 1 a la siguiente posición de bit). En segundo lugar, dos sumadores de 32 bits para los 32 bits superiores: uno agrega x + y, el otro agrega x + y + 1. Los tres sumadores funcionan en paralelo. Luego, cuando el primer sumador ha producido su acarreo, la CPU simplemente elige cuál de los dos resultados x + y o x + y + 1 es el correcto, y usted tiene el resultado completo. Por lo tanto, un sumador de 64 bits solo tarda un poco más que un sumador de 32 bits, no el doble de tiempo.

Las partes del sumador de 32 bits se implementan nuevamente como sumadores de suma condicional, utilizando múltiples sumadores de 16 bits, y los sumadores de 16 bits son sumadores de suma condicional, y así sucesivamente.

Answer 7

En caso de que un desglose del código ayude a alguien más, tome el ejemplo x=2, y=6 :

x no es cero, así que comienza a agregar a y

while(2) {

x & y = 2 porque

 x: 0 0 1 0 //2
y: 0 1 1 0 //6
x&y: 0 0 1 0 //2

2 <<1 = 4 porque << 1 desplaza todos los bits a la izquierda:

 x&y: 0 0 1 0 //2
(x&y) <<1: 0 1 0 0 //4

En resumen, guarde el resultado, 4 , en t con

int t = (x & y) <<1;

Ahora aplique el bit XOR y^=x :

 x: 0 0 1 0 //2
y: 0 1 1 0 //6
y^=x: 0 1 0 0 //4

Entonces x=2, y=4 . Finalmente, suma t+y reiniciando x=t y volviendo al principio del ciclo while:

x = t;

Cuando t=0 (o, al comienzo del ciclo, x=0 ), termine con

return y;

Answer 8

Para ser pedante, la especificación C no especifica cómo se implementa la suma.

Pero para ser realistas, el operador + en tipos enteros más pequeños o iguales al tamaño de palabra de su CPU se traduce directamente en una instrucción de suma para la CPU, y los tipos enteros más grandes se traducen en múltiples instrucciones de suma con algunos bits adicionales para manejar el desbordamiento .

La CPU usa internamente circuitos lógicos para implementar la adición, y no usa bucles, cambios de bits ni nada que tenga un parecido cercano con el funcionamiento de C.

Answer 9

Solo por interés, en el procesador Atmega328P, con el compilador avr-g ++, el siguiente código implementa la suma de uno restando -1:

volatile char x;
int main ()
{
x = x + 1;
}

Código generado:

00000090 <main>:
volatile char x;
int main ()
{
x = x + 1;
90: 80 91 00 01 lds r24, 0x0100
94: 8f 5f subi r24, 0xFF ; 255
96: 80 93 00 01 sts 0x0100, r24
}
9a: 80 e0 ldi r24, 0x00 ; 0
9c: 90 e0 ldi r25, 0x00 ; 0
9e: 08 95 ret

Observe en particular que la suma se realiza mediante la instrucción subi (resta constante del registro) donde 0xFF es efectivamente -1 en este caso.

También es interesante que este procesador en particular no tenga una instrucción addi , lo que implica que los diseñadores pensaron que hacer una sustracción del complemento sería manejado adecuadamente por los compiladores-escritores.

¿Aprovecha esto el complemento a dos u otras características dependientes de la implementación?

Probablemente sería justo decir que los compiladores-escritores intentarían implementar el efecto deseado (agregando un número a otro) de la manera más eficiente posible para esa arquitectura en particular. Si eso requiere restar el complemento, que así sea.