(void *) blog

Posted on by fortytwo_de


El resultado de sumar 00001111 (15) y 11110000 (240) es 255, es decir, 11111111.

Para entender la suma de bytes, primero explicaré la suma de bits:

Suma de bits

a b c d
1 0 1 0
0 1 1 0
0 0 0 0
1 1 0 1

a es el primer bit, bel segundo, c el resultado y d la llevada (carry).

Sin conocer aún las operaciones bitwise que se aplican, se pueden escribir los valores de c y d así:

  • c = a ? b
  • d = a ? b

"?" es una operación bitwise desconocida

Para descubrir las operaciones desconocidas, separo los dos valores de resultados.


Primero, con la tabla de valores de c:

a b c
1 0 1
0 1 1
0 0 0
1 1 0

Aislando la tabla de valores de c se puede descubrir que, efectivamente, la operación que se realiza sobre a y b para obtener b es XOR.


El mismo proceso con la tabla de valores de d:

a b d
1 0 0
0 1 0
0 0 0
1 1 1

¿Qué operación binaria solo devuelve 1 si las dos entradas son 1? Exacto, AND.


Ahora se pueden escribir las ecuaciones que determinan los valores de c y d:

  • c = a ^ b
  • d = a & b

Suma de bytes

Ahora sabemos que la operación para sumar dos bits es XOR, y la operación que determina las llevadas es AND.

Aplicando este conocimiento a los bytes; para sumar los bytes 00001111 y 1111000, se calculan los valores de c y d:

  • c = 00001111 XOR 11110000 = 11111111
  • d = 00001111 AND 11110000 = 00000000

En este caso, no hay llevadas, ya que los dos bytes no comparten ningún bit. Este es el caso más sencillo de suma binaria, pero hay que tener en cuenta el resto de casos. Otro ejemplo:

Suma binaria de 00000011 (3) y 00000001 (1). El resultado es 00000100 (4).

Aplicando las reglas de antes:

  • c = 00000011 XOR 00000001 = 00000010 (2)
  • d = 00000011 AND 00000001 = 00000010

Hmm. El resultado de sumar 3 y 1 no es 2, pero se ha obtenido "2" en el campo de llevadas, así que hay que volver a iterar.

Para que sumando las llevadas se obtenga el resultado correcto, hay que hacer bit shift de las llevadas, un orden de magnitud a la izquierda, porque (dado que se está trabajando con números binarios little endian) cada iteración es un orden mayor de magnitud.

Al mover las llevadas un bit a la izquierda se obtiene el resultado del siguiente operando para la suma.

  • d = 00000010 << 1 = 00000100
  • b = 00000100 (resultado de mover las llevadas un bit a la izquierda)
  • a = 00000010 (resultado de a XOR b en el paso anterior)
  • ---
  • c = 00000010 XOR 00000100 = 00000100 (4)
  • d = 00000010 AND 00000100 = 00000000

Ahora sí, el resultado del algoritmo es 4, como se esperaba.

Por lo tanto, una vez conocida la base teórica para la suma de bits, implementarlo en C es muy simple.


Posted on by fortytwo_de | Posted in Algoritmos, C, Matemáticas, Programación


6 Responses to Sumando bits y bytes

  1. Dirbaio says:


    OMG. Es BRUTAL! Una manera bonita de sumar sin usar “+”. Y parece que también funciona para números negativos! Very nice :D
    El coste del algoritmo es lineal en el número de bits, porque el peor caso es cuando un número es todo unos y el otro es 1. Pero para números cualquiera parece que hace muchas menos iteraciones :D

    He hecho una versión recursiva: http://hastebin.com/tehericapo.cpp


    • fortytwo_de says:


      :D :D

      Me alegro de que te guste! No había pensado sobre la complejidad del algoritmo, interesante.

      Y la implementación recursiva es un poco mindfuck, aunque supongo que consume algo de menos recursos (por aquello de no tener variables “temporales”)…

      Nice!


  2. santirivera says:


    c = 00000010 XOR 00000100 = 00000100 (4)

    10 XOR 100 = 100

    Ahí dejé de leer.


  3. Jerrell74 says:


    Hello, i noticed that your page loads very slow, it
    took around 9sec. to load this article. Do you know that website
    speed is major ranking factor for google now? If you
    speed up your page loading time you can rank higher and get more targeted traffic.
    There is simple method for faster loading,
    search for: Masitsu’s tricks


  4. 94Alfie says:


    Hi blogger, i must say you have high quality posts here.
    Your website should go viral. You need initial traffic only.
    How to get it? Search for: Mertiso’s tips go viral


Leave a Reply to Dirbaio Cancel reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>