Divide para sumar

Sigo maravillándome con los trucos para trabajar con los bits individualmente. Después de las últimas entradas escritas, traigo una con algo de trasfondo matemático.

Aritmética modular
La aritmética modular surge cuando trabajamos con los restos (o residuos) de una división con un divisor (o módulo) dado. Así, el residuo de 7 dividido entre (módulo) 3 es uno ya que 7=3·2+1. El teorema de la división nos indica que este valor existe y es único.
Los distintos lenguajes de programación incluyen tanto una operación de división como una operación de obtener el residuo. En la familia del C, se nota con el símbolo %.
Resulta que bajo un módulo dado, las operaciones de suma y multiplicación forman un anillo conmutativo. En todo caso, nos interesa la siguiente identidad

(a·b)%m == [(a%m)·(b%m)]%m

Bits y bytes
Por otra parte, cuando un número se almacena en base dos, cada bit se pondera a una potencia de dos. Esto es básico.


1001 = 1·8 + 0·4 + 0·2 + 1·1 = 9

Pero, ¿qué ocurre si obtengo el residuo de un número así? Probemos a hacer 9%7. El resultado es obviamente 2, pero ¿qué ocurre en las ponderaciones de bits?

9%7 = [1·(8%7) + 0·(4%7) + 0·(2%7) + 1·(1%7)]%7  = [1·1 + 0·4 + 0·2 + 1·1]%7 = 2%7 = 2

Es interesante ver que el bit que está con ponderacion 8 ahora pondera 1. Así que lo que estamos obteniendo es la suma de los dígitos octales módulo siete. Es decir, con números octales es fácil de calcular el resto módulo siete. Ejemplo:

0376252%7  = (3+7+6+2+5+2)%7 = 25%7 = 4

Si en vez de usar 7 usamos otro módulo, estaremos contando los dígitos en la base del siguiente número. En los números decimales tendríamos que usar módulo 9 y lo que obtenemos no es más que el criterio de divisibilidad por nueve: suma cifras y que éstas sean divisibles por nueve.

Divide para sumar
Ahora podemos utilizar este truco para sumar los bytes de un entero.

0xXXYYZZWW % 255 = (0xXX+0xYY+0xZZ+0xWW)%255

Siempre y cuando no llegue la suma a 255, la suma es exacta. Si fuera necesario sumar más de 255, se usarían operaciones AND y desplazamientos.  Se separa el número en dos, se suman dividiéndolos con módulo 65535 y luego se suman los resultados parciales. Algo más tedioso pero que se rentabiliza si de todas las maneras hay que hacer estas operaciones como ocurre en muchos algoritmos que trabajan con bits.