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. Si es un script que se ejecuta poco, esto no afectará el rendimiento general:

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.

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]

Dados dos conjuntos, A y B, y dos máscaras A1 y B1, en las que mediante un 0 se expresa que el elemento no pertenece al conjunto y mediante un 1 que sí pertenece, la operación OR (∨) nos proporciona la unión de ambos A ∪ B mientras que AND (∧) la intersección A ∩ B :

A1 = [0, 0, 0, 0, 0, 1, 1, 1, 1, 1]

B1 = [1, 0, 1, 0, 1, 0, 1, 0, 1, 0]

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

A1 ∨ B1 = 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

Sigue leyendo

Anti join

Las bases de datos relacionales (Oracle, SQL Server, Access, MySQL, etc) están basadas en el álgebra relacional. Dicha álgebra la desarrolló el ingeniero británico Edgar F. Codd en 1970 mientras trabajaba para IBM, pero el gigante azul tardó en desarrollar su primera base de datos relacional por preferir seguir explotando los ingresos de su base de datos IMS/DB. Mientras IBM se dedicaba a rentabilizar al máximo su inversión, otras empresas se llevaron el gato al agua al desarrollar sus propios sistemas relacionales a partir de los papeles de Codd. Habían cambiado para siempre las bases de datos.

Codd proporcionó las bases teóricas para las bases de datos relacionales y para los lenguajes que las manipulan. El rey de estos lenguajes es SQL, Structured Query Language. Ahora bien, lo llamo rey por lo extendido que está desde hace décadas, pues curiosamente tiene una carencia importante muy llamativa: no implementa el antijoin que define los papeles de Codd, sin que aparentemente tenga ninguna dificultad su implementación.

Si definimos el semijjoin (el left o right join de siempre) entre dos tablas A y B como:

Es decir, el left semijoin de las tablas A y B es la unión de todos los elementos a que pertenezcan a A junto con al menos uno de b  que pertenezca/n a B y que satisfagan una función sobre a U b. Esta función hace referencia al campo o campos de ambas tablas que hacemos servir para el join, usando sintaxis de MySQL sería

FROM A LEFT JOIN B ON (A.id = B.id)

El antijoin se definiría así:

Es decir, el antijoin de las tablas A y B es la unión de todos los elementos que satisfacen la función sobre a U b a que pertenezcan a A y no pertenezcan a B.

Desgraciadamente SQL no dispone de algo como:

FROM A ANTI JOIN B ON (A.id = B.id)

Y toca ir haciendo apaños como:

FROM A
WHERE A.id NOT IN(
SELECT id
FROM B)

O la supuesta optimización:

FROM A
LEFT JOIN B ON A.id = B.id
WHERE B.id IS NULL

Que producirá resultados inesperados si el campo pivote es nulo en algún registro de B.

Personalmente no veo que sea técnicamente más complicado implementar en los sistemas gestores de bases de datos un antijoin que otros tipos de join, pero el hecho es que de momento ninguno de los sistemas más extendidos lo incorpora en su dialecto SQL.


Editado el 22/01/2020:

En la última versión de MySQL, la 8.0.17, se va a optimizar el «apaño» antes explicado traduciendo la cláusula IN internamente como ANTIJOIN, según se comenta en la documentación. Podemos encontrar más información aquí.