Aritmética modular para entender el complemento a 2

Los ordenadores codifican internamente los números en binario. Los enteros pueden representarse mediante dos sistemas de representación: el complemento a 2 (Ca2 para abreviar) y el de signo y magnitud. Para los humanos es más amigable el segundo de ellos, pues consiste en reservar el primer bit para indicar si se trata de un positivo o negativo (0 o 1) y el resto es el valor absoluto del número. No obstante, en la mayoría de ordenadores hace ya bastantes años que se emplea el primero, pues goza de dos ventajas: un mayor rango de representación posible al mismo número de bits – pues tiene una única representación para el 0 – y mayor velocidad de ejecución por parte del microprocesador de las operaciones de resta y suma. En el presente artículo, se explicará cómo funciona el complemento a dos, porqué permite realizar las operaciones aritméticas más rápidamente y porqué su resultado debe interpretarse.

En primer lugar, para entender cómo funciona, el lector debe conocer lo básico de la aritmética modular y las clases de equivalencia. En caso de que lo desconozca o bien necesite refrescarlo, al inicio de este artículo se introducen.

Los procesadores representan los números enteros en 8, 16, 32 o 64 bits dependiendo del microprocesador. Para simplificar los ejemplos inicialmente se emplearán 3 bits, que permiten representar 23 = 8 dígitos, es decir, los números comprendidos entre el 0 y el 7. Si se excede el rango, debido a la aritmética modular se sigue obteniendo un resultado, por ejemplo:

  • 2 + 4 = 6 No sobrepasa el límite, el resultado es el esperado.
  • 4 * 2 = 0, pues 0 ≡ 8 (mod 8)
  • 4 + 5 = 1, pues 1 ≡ 9 (mod 8)

Sigue leyendo

Optimizaciones inútiles del código en PHP

En las aplicaciones donde la velocidad no es determinante – categoría a la que pertenecen muchas aplicaciones web – el código, antes que optimizado, debe estar estructurado. Como los requerimientos están cambiando frecuentemente, el tiempo del programador es mucho más importante (y costoso) que el tiempo de CPU. Además, lo que puede parecernos una optimización, a veces no lo es. Veamos un ejemplo con los desplazadores de bits.

La teoría nos dice que tanto la operación de multiplicación como la de división requieren cierto tiempo de computación, especialmente esta última. Ahora bien, si esta operación se hace con una potencia de 2, se convierte en algo trivial para la CPU gracias a los desplazadores, unos sencillos bloques combinacionales formados por unas pocas puertas lógicas.

Los desplazadores tienen una señal de entrada y una de salida de n bits ambas. La señas de salida se obtiene desplazando los bits de entrada m veces hacia la derecha o hacia la izquierda El desplazamiento a la izquierda equivale a multiplicar por 2m mientras que a la derecha realiza la división entera por 2m. En el caso del desplazamiento a la derecha o división, en función del valor que se asigne a los «nuevos» bits, existen dos tipos de desplazadores:

  • Lógicos: Se ponen a 0.
  • Aritméticos: Se ponen al mismo valor que el bit de más peso de la entrada. Sirven para que los números codificados en complemento a dos conserven el signo.

Desplazador aritmético y lógico de 4 bits

Dos desplazadores de 4 bits: El de arriba lógico y el de abajo aritmético. Ambos desplazan 01 (2(10) bits a la derecha, i.e., dividen por 2.

Sigue leyendo

Cómo comentar el código

En la lista de libros frecuentemente citados y raramente leídos, probablemente encontraríamos desde «El fin de la historia y el último hombre», de Francis Fukuyama, hasta «Code Complete», de Steve McConnell. Este último es el que voy a citar aquí, sin haberlo leído para seguir la tradición, concretamente su muy extendida afirmación de que los comentarios no tan solo no son necesarios sino que pueden conseguir el efecto contrario: un código complejo que el programador no trabaja para simplificarlo por tener a su disposición el camino, inicialmente más breve, de los comentarios.

En mi humilde opinión, aunque estoy de acuerdo en gran parte con la opinión de McConnell y otros, los comentarios sí son necesarios. Estos deben describir el porqué o describir qué se está haciendo, no el cómo, pues es el cómo lo único que puede delegarse a un código claro y descriptivo. Cuando el proyecto carece de documentación o no se mantiene actualizada, los comentarios que explican el porqué son aun más necesarios.

A continuación, veamos algunos ejemplos prácticos para ilustrar mi opinión:

class Model_Session
{

   /**
    * Sigue el patrón singleton para encapsular la sesión.
    * No extiende Model_Signia_Abstract porque debe definir construct privado.  
    */
   private $calledClass;

   protected function __construct($options)
   {
      $this->calledClass = explode('_', get_called_class())[1];
   }

   final static function getInstance($options = null)
   {
      static $instances = array();

      $calledClass = get_called_class();

      if (!isset($instances[$calledClass])) {
         $instances[$calledClass] = new $calledClass($options);
      }

      return $instances[$calledClass];
   }

   public function __clone()
   {
      trigger_error("An instance of the class " . __CLASS__ . " already exists.", E_USER_ERROR);
   }

   protected function set($value)
   {
      $_SESSION[$this->calledClass] = $value;
   }

   public function get($value)
   {
      if (isset($_SESSION[$this->calledClass][$value])) {
         return $_SESSION[$this->calledClass][$value];
      } else {
         return false;
      }
   }

   public function isLogged()
   {
      return isset($_SESSION[$this->calledClass]);
   }
   
   public function delete($key)
   {
      unset($_SESSION[$this->calledClass][$key]);
   }
   
   public function logout()
   {
      unset($_SESSION[$this->calledClass]);  
   }
   .
   .
   .
}

Algunos consideran que singleton es un antipatrón de diseño, pero este código está ahora mismo solucionando necesidades reales de empresas y soy de la opinión de que la teoría existe para ayudarnos, no para interferir en aquello por lo que nos pagan. En la misma línea, aunque trigger_error debería evitarse, en los métodos mágicos prefiero lanzar un error a lanzar una excepción. Aclarado esto, regresemos al tema que ocupa este artículo. Con la primera línea del comentario explico por qué y para qué uso el patrón:

Sigue el patrón singleton para encapsular la sesión.

La segunda línea está pensada para responder tanto el porqué que me pueda plantear yo cuando revise el código tiempo después y no recuerde por qué lo programé así, como el que se pueda plantear otro programador que vea esta clase por primera vez:

No extiende Model_Signia_Abstract porque debe definir construct privado.

El resto de la clase no tiene más comentarios y tampoco le hacen falta, pero, ¿qué sucede cuando los nombres de las variables y métodos no son descriptivos? Que nos vemos obligados a crear comentarios que clarifiquen cómo funciona la rutina. Comparemos estos dos métodos:

function permsM($m)
{
      $perms = [];
      
      foreach (['add', 'view', 'edit', 'delete'] as $a) {
         if (isset($this->get('permissions')[$a]) && in_array($m, $this->get('permissions')[$a])) {
            $perms[] = $a;
         }
      }

      return $perms;
}

Probablemente el ejemplo esté un poco forzado, pero sin duda demuestra que, o bien añadimos comentarios por doquier, o bien usamos nombres descriptivos:

public function getPermissionsForModule($sModule)
{
      $aPermissions = [];
      
      foreach (['add', 'view', 'edit', 'delete'] as $action) {
         if (isset($this->get('permissions')[$action]) && in_array($sModule, $this->get('permissions')[$action])) {
            $aPermissions[] = $action;
         }
      }

      return $aPermissions;
}

Cuando tenía unos 9 años hice mi primer «programa», lo sufrió un Zx Spectrum 128, su cantidad de memoria estaba contenida en su nombre, en Kilobytes. Con semejante restricción, entiendo que en la época tenía lógica optimizar el consumo de memoria incluso recortando el nombre de las funciones y variables, pero a día de hoy eso no tiene ningún sentido. Además, tanto los IDE como sencillos editores (por ejemplo Notepad++), disponen de la funcionalidad de autocompletar texto, que nos ayuda a recordar y escribir correctamente los nombres de variables, funciones, métodos y clases sin importar cuán largos sean. Por lo tanto, a día de hoy no hay excusas para no usar nombres descriptivos.

En este sentido, las constantes ayudan enormemente:

if ($file['error'] === 0 { //¿Mande? ¿Fue bien o mal?

if ($file['error'] === UPLOAD_ERR_OK {

Podemos llegar a ser más papistas que el Papa con el código que se explica a si mismo:

if ($file['size'] > 5242880) { // 5 MB

if ($file['size'] > 5*1024*1024) {

Otros comentarios necesarios

– Cuando, por falta de tiempo, se ha tenido que programar de forma poco óptima, indicarlo ayudará más adelante, cuando el proyecto haya sido entregado, a reconocer las partes que necesitan refactoring más urgentemente.

– Existen expresiones que son complejas y no hay azúcar sintáctico que las simplifique, como por ejemplo las expresiones regulares; en estos casos, comentar qué se está buscando aumentará la productividad de todo el equipo.

– Finalmente, cuando hemos copiado un código con licencia que lo permita, es de caballeros citar el autor y la fuente (si es que no estamos obligados directamente por la misma).

En definitiva, si cada vez que escribimos un comentario nos preguntamos si es realmente necesario o, si por el contrario, está encubriendo un código poco legible, conseguiremos elaborar software más fácil de mantener, tanto para nosotros como para quienes vengan después. Si describe cómo procesa, lo más probable es que nos estemos haciendo trampas.

Leyendo Don’t make me think

Hace años que no leo nada acerca de usabilidad, desde que finalicé los estudios. Ahora estoy leyendo «Don’t make me think, Revisited» de Steve Krug, un reputado especialista en usabilidad. Es la tercera edición que el autor hace del clásico que publicó en el año 2000. En esta nueva edición hace un repaso sobre los mismos principios añadiendo la usabilidad web para móviles y poniendo ejemplos más actuales.

Bastante ameno y muy ilustrado, no se trata de un extenso tratado sino de un compendio de los aspectos más importantes de la navegación y distribución de la información.

En vez de extenderme más en la descripción del libro pondré un ejemplo de su utilidad. Varios de los estudios que el autor ha hecho para sus clientes han incluido la observación del uso que diferentes usuarios dan a su web. Puede llegarnos a sorprender el modus operandi de algunos usuarios pues tendemos a pensar que la forma en que nosotros usamos una web es la más lógica o intuitiva y por lo tanto también la más común. Sólo darse cuenta de como caemos en este error compensa el tiempo y el dinero que cuesta el libro.

Leí en algún sitio que si sólo fueras a leer un libro sobre usabilidad debería ser este. Pues eso, imprescindible para diseñadores y desarrolladores web.

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.