¿Cómo funciona el código?

Answer 1

Esta es una simulación de software de un dispositivo de hardware llamado “medio sumador”, o más exactamente, una matriz de medios sumadores tan anchos como las variables de entrada. Ahora que conoce el término, busque en Google “medio sumador” y mire los circuitos y las tablas de verdad que encontrará.

La expresión “a ^ b”, donde el cursor es en realidad el operador XOR bit a bit, calcula el nuevo valor de bit de salida en esta posición particular en la palabra binaria. (XOR es idéntico a la adición modular de base-2). La expresión “a & b” es una operación AND a nivel de bit, que calcula la salida de acarreo de la suma en cada posición de bit. Luego, la parte “<< 1" desplaza todos los bits de acarreo 1 posición hacia la izquierda (multiplicándolos efectivamente por 2), dándoles el valor numérico correcto.

Entonces, la entrada es dos números binarios arbitrarios. El cálculo en la línea 3 genera dos nuevos números binarios cuya suma es la misma que las dos entradas. Pero es probable que el segundo valor (los bits de acarreo) tenga más ceros que unos en él. Como la función se llama a sí misma de forma recursiva, los bits de acarreo “1” se desplazan hacia la izquierda hasta que encuentran un lugar donde se pueden agregar, mientras que hay una cadena de bits “0” a la derecha del valor “b”. Una vez que tiene una cadena ininterrumpida de ceros en “b” que comienza desde el extremo derecho, esos ceros nunca pueden cambiar a unos, y por lo tanto la porción inferior de la misma longitud de “a” tampoco puede cambiar más.

Finalmente, la entrada “b” debe convertirse en cero y la recursión se detiene. Debido a que la suma de “a” y “b” es constante para cada llamada, y “b” ahora es cero, “a” solo es la suma de las dos entradas.

Nota: este no es un sumador de transferencia de ondas, que solo agrega un bit a la vez, y toma N ciclos para agregar N bits, incluso si no hay acarreos. Este sumador agrega todos los bits en paralelo, y se puede hacer en un solo ciclo si todos los bits de acarreo son cero. Por lo general, tomará algunos ciclos más para terminar de propagar los acarreos. El peor de los casos sigue siendo N ciclos, pero eso solo sucede para un posible par de entrada (creo).

Dave

Answer 2

La idea crucial es que la operación XOR es solo el módulo de adición bit a bit 2. En otras palabras, dados dos bits [math] a_k [/ math] y [math] b_k [/ math], el valor de [math] a_k [/ math ] ^ [matemática] b_k [/ matemática] es igual a [matemática] a_k + b_k [/ matemática] a menos que ambos sean iguales a 1, en cuyo caso vuelve a cero.

Esto es exactamente lo que debe hacer si olvida llevar dígitos mientras agrega dos números en papel. Entonces, ¿qué dígitos necesitamos llevar? Precisamente los que se desbordan, es decir, cada vez que el bit se establece en [math] a [/ math] y [math] b [/ math].

Para aislar eso, usted Y ellos juntos, gire a la izquierda una vez para transportar, y agregue los bits transportados nuevamente. Como un aparte, así es básicamente cómo funciona un sumador de transporte de ondas en electrónica.

Answer 3

Este programa utiliza operadores binarios basados ​​en c. Entonces, la mejor manera de aprender cómo se hace esto es recorrerlo.

Entonces intentemos 2 + 2

^ es un Xor binario que dice que todos los ceros se convierten en unos

& es el binario Y que dice si hay un 1 en la misma posición de cada número

<< desplaza el número binario sobre el número de lugares que en este caso es 1

2 = A, 2 = b

b no es igual a 0, así que no regrese

2 en binario es 0010

Entonces Xor es 0

Y es 0010

turno sobre 1 es 0100

Entonces 0 = A, 4 = b

b no es igual a 0

Xor es 0000 ^ 0100 = 01000 = 4

Y = 0 porque 0 y 4 nada en común

cambio más sigue siendo 0

A = 4 y B = 0

B es igual a 0, entonces devuelve 4

Answer 4

Esta es una suma de bits, divide ambos números en dos y los combina,

a ^ b: obtiene todos los bits no comunes para ambos números

(a & b) << 1: obtiene todos los bits comunes para ambos números y los suma "<< 1" es igual a "* 2"

entonces necesita “sumar” estos nuevos números