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

Cuando la comprensión de cómo los operadores primitivos, tales como +, -, *y /son implementados en C, me encontré con 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 usando directivas de ensamblaje generadas por el compilador durante mucho tiempo!

¿El +operador está implementado 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?

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

Pero para ser realistas, el +operador en tipos enteros menores 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 se parezca mucho a cómo funciona C.

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 hace xor bit a bit, puede obtener la suma sin acarreo. Y si lo hace bit a bit y puede obtener los bits de acarreo.

Ampliando esta observación para números multibit ayb

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

Una vez bes 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;

Lleva pedacitos. El bit de acarreo es 1 si 1 bit a la derecha en ambos operandos es 1.

y ^= x;  // x is used now

Adición sin llevar (llevar bits ignorados)

x = t;

Reutilizar x para configurarlo para llevar

while(x)

Repita mientras haya más bits de transporte

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 + realmente funciona en segundo plano

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

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

No. Esto se traduce a la addinstrucción de máquina nativa , que en realidad utiliza el sumador de hardware, en el 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 en su mayoría están hechas de transistores. El sumador completo tiene medios sumadores.

Para obtener un tutorial básico sobre puertas lógicas y sumadores, consulte esto . 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 los dos bits dados. Las posibles combinaciones son:

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

Entonces, ¿cómo funciona el medio sumador? Bueno, que se compone de tres puertas lógicas, el and, xory el nand. El nand da una corriente positiva si ambas entradas son negativas, lo que significa que esto resuelve el caso de 0 y 0. xorDa 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 andda una salida positiva sólo si ambas entradas son positivas, por lo 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 semisumador una y otra vez. Ahora bien, esto tiene un acarreo. Cuando sumamos 1 y 1, obtenemos un acarreo 1. Entonces, lo que hace el sumador completo es, toma el acarreo del medio sumador, lo almacena y lo pasa como otro argumento al medio sumador.

Si está confundido, ¿cómo puede pasar el acarreo? Básicamente, primero agrega los bits usando el medio sumador y luego agrega la suma y el acarreo. Entonces ahora ha agregado el acarreo, con los dos bits. Así que haz esto una y otra vez, hasta que terminen los bits que tienes que agregar, y luego obtienes el 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 ALU(la mayor parte de CPU), memoria, buses, etc.

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

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

C usa una máquina abstracta para describir lo que hace el código C. Entonces, no se especifica cómo funciona. Hay "compiladores" de C que en realidad compilan C en un lenguaje de programación, por ejemplo.

Pero, en la mayoría de las implementaciones de C, +entre dos enteros más pequeños que el tamaño de entero de la máquina se traducirá en una instrucción de ensamblaje (después de muchos pasos). La instrucción de ensamblaje se traducirá a código de máquina y se incrustará en su ejecutable. Ensamblador es un lenguaje "eliminado en un paso" 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 luego 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 aritmética lógica.

La unidad aritmética lógica puede tener sumadores y multiplicadores separados, o puede mezclarlos.

La unidad 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 aritmética lógica como en el decodificador de instrucciones (así como las partes que he pasado por alto) está grabado en el chip en 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 operan y genera transistores y líneas de interconexión.

El lenguaje de descripción de hardware puede contener cambios y bucles que no describen las 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 inexactitudes. Esto se debe a mi propia incompetencia (he escrito tanto hardware como compiladores, pero no soy un experto en ninguno de los dos) y porque todos los detalles tomarían una carrera o dos, y no una publicación SO.

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

Casi cualquier procesador moderno que pueda ejecutar código C compilado tendrá soporte incorporado para la adición de números 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 adición de enteros, pero no es así como se realiza normalmente la suma de enteros. De hecho, el enlace de funciones 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 xey, puede descomponerlo en los bits que tienen en común y los bits que son exclusivos de x o y.

La expresión x & y(AND bit a bit) da los bits comunes ax 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 + yse puede reescribir 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 ax o y.

(x & y) << 1 es el doble de los bits que tienen en común (el desplazamiento a la izquierda por 1 se multiplica efectivamente 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 cambiar. Puede pensar en el primer valor como los acarreos 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, en cuyo punto y contiene la suma.

El código que encontró intenta explicar cómo un hardware informático muy primitivo podría implementar una instrucción de "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, usa números decimales y ha aprendido a sumarlos: para sumar dos números, suma los dos dígitos más bajos. Si el resultado es menor que 10, anote el resultado y proceda a la siguiente posición del dígito. Si el resultado es 10 o más, anote el resultado menos 10, proceda al siguiente dígito, compre recuerde agregar 1 más. Por ejemplo: 23 + 37, sumas 3 + 7 = 10, escribes 0 y recuerdas agregar 1 más para la siguiente posición. En la posición de las decenas, agrega (2 + 3) + 1 = 6 y anótalo. El resultado es 60.

Puede hacer exactamente lo mismo con los 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 dígito tras otra. Y así es como lo haría un hardware informático realmente primitivo.

Este código funciona de manera diferente. Sabes que la suma de dos dígitos binarios es 2 si ambos dígitos son 1. Entonces, si ambos dígitos son 1, agregarías 1 más en la siguiente posición binaria y escribirías 0. Eso es lo que hace el cálculo de t: Encuentra todos los lugares donde ambos dígitos binarios son 1 (que es el &) y los mueve a la siguiente posición de dígito (<< 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 excluyente o.

Pero todos los 1 que tuvo que manejar en la posición del siguiente dígito no se han manejado. Aún deben agregarse. 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 de esa manera? 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 bits 1), la primera iteración borra el bit 0 de y y establece x en 2. La segunda iteración borra el bit 1 de y y establece x en 4. Y así sucesivamente. Se necesitan 32 iteraciones para obtener el resultado. Sin embargo, cada iteración tiene que procesar todos los bits de xey, lo que requiere mucho hardware.

Un procesador primitivo haría las cosas tan rápido como usted hace 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 de la posición del 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 los 32 bits más bajos. Ese sumador de 32 bits produce una suma y un "acarreo" (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 más altos: uno suma x + y, el otro suma 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 + yox + 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.

Las partes sumadoras de 32 bits se implementan de nuevo como sumadores condicionales, utilizando múltiples sumadores de 16 bits, y los sumadores de 16 bits son sumadores condicionales, y así sucesivamente.

Mi pregunta es: ¿el operador + está implementado como el código publicado en la MAYORÍA de las implementaciones?

Respondamos la pregunta real. Todos los operadores son implementados por el compilador 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 realmente sucede 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 adicionales aquí. Es perfectamente legal para el compilador traducir esto a:

some_other_function(18, x * 2);

O tal vez el compilador nota que llamas a la función foovarias veces seguidas y que es una aritmética simple y generará instrucciones vectoriales para ella. O que el resultado de la suma se utilice para indexar matrices más adelante y lease utilizará la instrucción.

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

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

xno es cero, así que comience 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 = 4porque << 1desplaza todos los bits a la izquierda:

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

En resumen, esconder ese resultado, 4en tla

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

Ahora aplique el XOR bit a bit 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, sume t+yreiniciando x=ty volviendo al comienzo del whileciclo:

x = t;

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

return y;

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 subiinstrucción (resta constante del registro) donde 0xFF es efectivamente -1 en este caso.

También es de interés que este procesador en particular no tiene una addiinstrucción, lo que implica que los diseñadores pensaron que hacer una resta 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.