Máscaras de bits

Una máscara de bits son datos para operaciones a nivel de bits. Por ejemplo para el conjunto de los 10 primeros números naturales:

U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

La máscara que marca los impares es:

M = [1, 0, 1, 0, 1, 0, 1, 0, 1, 0]

Mediante la operación NOT sobre la máscara obtenemos los pares:

M = [0, 1, 0, 1, 0, 1, 0, 1, 0, 1]

Dadas dos máscaras, A y B, la operación OR (∨) nos proporciona la unión de ambas A ∪ B mientras que AND (∧) la intersección A ∩ B :

A = [0, 0, 0, 0, 0, 1, 1, 1, 1, 1]

B = [1, 0, 1, 0, 1, 0, 1, 0, 1, 0]

A ∧ B = A ∩ B = [0, 0, 0, 0, 1, 0, 1, 0]

A ∨ B = A ∪ B = [1, 0, 1, 0, 1, 1, 1, 1, 1, 1]

Las máscaras de bits tienen diferentes usos.

Sirven para definir rangos de IPs y ACL

ACL es el acrónimo de listas de control de acceso. En el protocolo TCP/IP las direcciones IP vienen acompañas de su máscara. Si ejecuto ifconfig en mi ordenador aparece la siguiente información:

ifconfig

IP y máscara

Es gracias a la máscara que los demás ordenadores de esta red pueden saber si el mío pertenece a la misma red local o a una red remota. Veamos como lo hace:

11000000.10101000.00000001.01100111 => 192.168.1.103 IP

11111111.11111111.11111111.00000000 => 255.255.255.0 Máscara de red

Mediante ceros las máscaras de red indican qué octeto es el significativo para identificar al ordenador, en este caso es el último octeto, cuyo valor es 103. Mientras que con unos indica el identificador de la red, que en este ejemplo es el de las redes locales o redes de clase C: 192.168.1

Sirven para gráficos 2D

En los juegos de no hace tantos años, antes de la llegada de las 3D, mediante una máscara de bits se indicaba que parte del sprite debe transparentar con el fondo por el que se mueve.

Sprites y máscaras de bits

Sprites y máscaras de bits

Aún hoy en día se siguen usando, por ejemplo cuando hace pocos meses Google añadió este juego a Google Maps:

Ms Pac-Man paseando por Madrid se encuentra la sede del PP…

cazando corruptos

¡Y no puede evitar ponerse cazar fantasmas corruptos pululando por la calle Génova!

Sirven para hacer código más legible

Se usan en funciones y métodos que esperan varios parámetros booleanos. La principal ventaja es simplificar el uso de la función, secundariamente se consigue una menor carga de la pila. Si tenemos en PHP la función:

function func ($param1, $param2, $param3, $param4)

Cuando la invoquemos lo más probable es que no nos acordemos de los parámetros y su orden. Es más práctico algo como esto:

const BIT_1 = 0b0001; // 1
const BIT_2 = 0b0010; // 2
const BIT_3 = 0b0100; // 4
const BIT_4 = 0b1000; // 8

function func ($bits) {
  if ($bits & BIT_1) {
    // Haz esto.
  }
  if ($bits & BIT_2) {
    // O esto otro.
  }
  if ($bits & BIT_3) {
    // También esto.
  }
  if ($bits & BIT_4) {
    // Y esto si también te lo piden.
  }
}

func(BIT_1 | BIT_3);

En PHP los operadores de bit AND y OR son & y | respectivamente. Muchas de las funciones incluidas en PHP usan está técnica, al igual que en otros lenguajes. He aquí unos ejemplos:

filter_var($string, FILTER_SANITIZE_STRING, FILTER_FLAG_STRIP_HIGH | FILTER_FLAG_STRIP_LOW)

html_entity_decode($string, ENT_QUOTES | ENT_XML1, 'UTF-8')

El error_reporting para especificar el nivel de errores en php.ini y la función error_reporting() para modificarlo en tiempo de ejecución.

Sirven para el control de permisos

Usar máscaras de bits y operaciones a nivel de bit para controlar los permisos de usuarios o de los grupos a los que pertenecen puede llegar a ser inviable en aplicaciones realmente grandes, pero donde sea cómodo aplicarlas se conseguirá una velocidad y reducción del tamaño de la base de datos sin igual. En el caso de la base de datos permiten pasar de tener una o más tablas donde almacenar los permisos a un solo campo en la tabla de usuarios, permitiendo olvidarnos entonces de costosas consultas con Joins.

Aunque su uso para estos menesteres no sea recomendable, veamos a modo de curiosidad cómo funcionan. La siguiente tabla presenta unos permisos mapeados para un gestor de contenidos:

cambiar permisos crear perfil editar perfil borrar perfil crear borrador
512 256 128 64 32
editar entrada borrar entrada publicar entrada editar entrada borrar entrada
16 8 4 2 1

Si en la campo “permisos” de un usuario tenemos el número 14, sabemos que este en binario es 1110. También sabemos que el número máximo es 512, 1000000000 en binario, por lo tanto concatenemos por la izquierda los ceros que faltan: 0000001110. Sigue siendo 14 en binario y si ponemos cada dígito en la tabla donde mapeamos los permisos, tendremos que con 1, es decir, activos, están los que permiten editar, borrar y publicar una entrada. A los demás permisos les corresponde un cero y por lo tanto el usuario no los tiene. Un usuario con todas las concesiones sería 1111111111, por lo tanto en el campo correspondiente de la tabla “usuarios” tendría almacenado el número 1023.

Antes hemos visto como implementa PHP los operadores bit a bit; realmente todos los lenguajes los implementan, observemos ahora la siguiente consulta SQL en MySQL:

SELECT * FROM usuarios WHERE 512 & permisos

Esta consulta nos daría todos los usuarios que tienen el 512, “cambiar permisos”, activado. El operador a nivel de bits & devolverá verdadero sólo en los casos en que sean 1 los bits a su izquierda y lo sean también en la misma posición a la derecha. Recordemos que 512 en binario es 1000000000 por lo que la condición del WHERE será sólo verdadera en los registros cuya columna “permisos” el bit más significativo (el de la izquierda) valga 1. Por supuesto también se pueden usar otros operadores lógicos, no sólo AND.

Como hemos visto, aunque las operaciones a nivel de bit parezcan más de tiempos en los que los recursos de los ordenadores, RAM y CPU, eran muy limitados, siguen teniendo su utilidad.

Zen, matemáticas y la paradoja de Sorites

Montón de arena o duna o n granos de arena

¿Montón de arena? ¿Duna? ¿N granos de arena?

Hace años leí algunos capítulos de un fragmento de un libro Zen escrito en algún momento entre los siglos XVI y XIX, ya no recuerdo, de la escuela Soto o Rinzai, tampoco lo recuerdo, de un autor que, como probablemente habrás adelantado, tampoco recuerdo, pero sí, era japonés. En definitiva, muy Zen todo. Lo que sí recuerdo bien es un símil realizado con la evolución de un fuego recién empezado con unos leños hasta su consumición completa. ¿En qué momento podemos decir que dejaron de haber leños para haber sólo ceniza? Creo que con este ejemplo el autor quería hacer notar las limitaciones que nuestros conceptos mentales tienen para ayudarnos a entender la realidad.

Bastantes años después he caído, navegando por Internet, en la paradoja de Sorites. Esta paradoja entiendo que quiere hacernos caer en la cuenta de algo muy parecido, poniendo como ejemplo no la combustión de un pequeño fuego sino un montón de arena. Sorites es como se pronuncia en griego σωρείτης palabra que significa montón o cúmulo. La paradoja parte del hecho de que estaremos todos de acuerdo en que:

  1. Dos o tres granos de arena no son un montón.
  2. 100.000 o 1.000.000 sí lo son.
  3. Si dos o tres granos de arena – llamemos n a esos dos o tres – no son un montón, tampoco lo serán n+1
  4. Un montón de n granos no dejará de serlo por quitarle uno (n-1)

Mediante inducción matemática se comprueba que la primera y tercera característica niegan la segunda, es decir, que 100.000 granos (ni un millón) forman un montón.

Llamemos a ser un montón tener la propiedad P. La primera característica nos dice que para n = 1 no existe la propiedad P, y que tampoco existe para n = 2 ni para n = 3. La tercera nos dice que dado que Pn no es un montón tampoco lo será Pn+1 = n+1 Tenemos:

  1. ¬P(1)
  2. ¬P(2)
  3. ¬P(n) ⇒ ¬P(n+1)

Supongamos que hay un número mínimo de granos de arena a partir del cual sí se verifica P, llamaremos m a ese número. Tenemos entonces que m-1 no es un montón y a partir de m granos sí lo es. También sabemos por la característica 1 que m > 1 y por la 3 sabemos que m -1 debe cumplir:

P(m-1) ⇒ P(m -1 + 1)

Es decir, que P(m-1) = P(m) y esto es una contradicción pues hemos impuesto que m es el elemento mínimo a partir del cual tenemos la propiedad P (es un montón) y por debajo de m granos no tenemos esa propiedad.

Por el mismo método de la inducción matemática se demuestra a partir de las características segunda y cuarta de un montón que la primera es falsa, es decir, que tan solo dos o tres granos de arena sí son un montón. Incluso que ningún grano también lo es.

Por lo tanto, no sólo conceptos como la belleza o la armonía son difíciles de definir, sino que identificar conceptos que representan objetos físicos como la madera o la ceniza, incluso los medibles como la gordura o la delgadez (peso), o un montón (número de elementos que lo forman) nos pueden resultar evidentes cuando realmente no lo son.

Las potencias de la unidad imaginaria como clase de equivalencia

El número imaginario i es aquel que permite resolver, entre otras cosas, la ecuación:

i2 = -1

Por lo tanto i = √-1

Podemos ver que sus potencias enteras son:

i0 = 1

i1 = i (= √-1)

i2 = -1

i3 = i * i2 = i * (-1) = -i

i4 = i2 * i2 = -1 * (-1) = 1

i5 = i2 * i3 = -1 * (-i) = i

in = …

Si seguimos la serie vemos que emerge un patrón: 1, i, -1, -i, …

Así como vimos que las congruencias se podían tratar como clases de equivalencia, vemos aquí que las potencias de i se pueden tratar como la clase de equivalencia Z4

Sabemos que Z4 = {[0], [1], [2], [3]} es decir, el total de restos posibles de 4 y sabemos una n potencia de i que pertenece a cada clase:

0 = i0

1 = i1

2 = i2

3 = i3

Con todo esta información no habrá potencia que se nos resista. Si queremos calcular i54 sólo tendremos que calcular el resto de la división de 54 entre 4, que es 2 y por lo tanto pertenece a la misma clase que i2 , por lo que podemos afirmar que i54 = i2 = -1 También podemos afirmar que i54 es congruente con i2 La fórmula general es:

in = i4 mod (n)

Esto también puede enfocarse desde una perspectiva más gráfica. Multiplicar por i es rotar en el plano 90º hacía atrás y multiplicar por -i es avanzar 90º Por más que rotemos siempre acabaremos en uno de los 4 puntos:

El número imaginario en el plano cartesiano complejo

El número imaginario i en el plano cartesiano complejo