Archivo por meses: diciembre 2010

Desplazando bits

Hace mucho tiempo, cuando empecé a programar en C, leí una curiosa advertencia sobre los operadores de desplazamiento de bits, los famosos >> y <<. Se afirmaba allí que, al desplazar una variable con ellos, los bits que salían se perdían (lógico, siendo un desplazamiento), pero que los bits que entraban por el lado opuesto tenían un valor indefinido, que podía ser cero o uno según la implementación.

Es cierto que todos los programadores asumen que lo que entra es cero siempre; pero pese a todo, yo, que tiendo a ser demasiado cauto, opté por añadir siempre una máscara AND para poner a cero los bits entrantes y así evitarme sorpresas.

Sin embargo, hace unos días, mientras optimizaba unas rutinas que hacen uso de desplazamientos, decidí investigar más a fondo el tema, porque a fin de cuentas una máscara consume ciclos de reloj, así que si había alguna forma de evitarla siempre sería una mejora. Y lo que descubrí me dejó gratamente sorprendido, porque en realidad el valor de los bits que entran no depende del compilador, sino que está perfectamente definido en el estándar.

Cuando se utiliza el desplazamiento hacia la izquierda (<<), por el lado derecho siempre entran ceros. Ahí nunca hay problemas. Por otro lado, cuando se utiliza el desplazamiento hacia la derecha (>>) en una variable sin signo (por ejemplo, en un unsigned int), por la izquierda también entran siempre ceros.

Sin embargo, cuando utilizamos variables con signo (por ejemplo, short int) en un desplazamiento hacia la derecha, los bits que entren por la izquierda serán una copia del bit de mayor peso del valor original. Así, si teníamos un número negativo (su bit de mayor peso está a uno), al desplazarlo hacia la derecha seguirá siendo negativo, porque los bits entrantes serán unos; en cambio, si era un número positivo (su bit de mayor peso está a cero) los bits entrantes serán cero.

Supongo que la razón de hacerlo así es que, si se utilizan rotaciones para hacer divisiones, se conserva el signo.

Este código ilustra perfectamente lo dicho aquí:

#include <stdio.h>

void desplaza(unsigned int o) {

  signed int s1,s2;
  unsigned int u1,u2;

  s1=s2=u1=u2=o; // asignamos el mismo valor a las cuatro variables

  s1>>=4; // desplazamos cuatro veces cada una de ellas
  s2<<=4;
  u1>>=4;
  u2<<=4;

  printf("Con signo:ntdesplazamiento a la derecha   %08Xn",s1);
  printf("tdesplazamiento a la izquierda %08Xn",s2);
  printf("Sin signo:ntdesplazamiento a la derecha   %08Xn",u1);
  printf("tdesplazamiento a la izquierda %08Xnn",u2);
}

int main() {

  printf("nDesplazamiento de 4 posiciones.n");
  printf("Valor original: 0xA50000A5 (bit de mayor peso a uno).n");
  desplaza(0xA50000A5);
  printf("nValor original: 0x5A00005A (bit de mayor peso a cero).n");
  desplaza(0x5A00005A);

  return 0;
}

La salida es la siguiente, donde se aprecia claramente como el bit superior se replica en los desplazamientos a la derecha de las variables con signo, pero no en el resto de los casos:

Desplazamiento de 4 posiciones.
Valor original: 0xA50000A5 (bit de mayor peso a uno).
Con signo:
  desplazamiento a la derecha   FA50000A
  desplazamiento a la izquierda 50000A50
Sin signo:
  desplazamiento a la derecha   0A50000A
  desplazamiento a la izquierda 50000A50

Valor original: 0x5A00005A (bit de mayor peso a cero).
Con signo:
  desplazamiento a la derecha   05A00005
  desplazamiento a la izquierda A00005A0
Sin signo:
  desplazamiento a la derecha   05A00005
  desplazamiento a la izquierda A00005A0