====== Operaciones con bits ======


===== Operadores de bits =====

^ Símbolo ^ Función ^ latencia (ciclos) ^ significado ^
|  ''&''  | and |  1  | y bit a bit |
|  ''|''  | or |  1  | o bit a bit |
|  ''^''  | xor |  1  | o exclusivo bit a bit |
|  ''%%<<%%''  | shift left |  1  | desplazamiento a la izquierda |
|  ''%%>>%%''  | shift right |  1  | desplazamiento a la derecha |
|  ''~''  | complement |  1  | negación bit a bit |

Como se puede apreciar, estas operaciones son muy eficientes en términos de su latencia en ciclos del
reloj.

===== Máscaras de bits =====

Los operadores ''&'' y ''|'' son especialmente útiles en conjunto con //máscaras de bits//.  Una máscara de bits es un número entero con ciertos bits en 1 y el resto en 0.  Se usan para borrar bits de un entero o para colocarlos en 1:

  * x & MASK : borra aquellos bits de x que en la máscara MASK aparezcan en 0.
  * x | MASK : colocar en 1 los bits de x que en MASK aparezcan en 1.

Por conveniencia se usan números hexadecimales para expresar las máscaras.  Ejemplos:

^ Operación ^ Resultado ^ Significado
|  0xb3a7 & 0x0ff0  |  0x03a0  | Se borran las cifras que estan en 0 en la máscara |
|                   |          | y se dejan intactas las cifras que están en f |
|  0xb3a7 ''|'' 0x0ff0  |  0xbff7  | Se dejan intactas las cifras que están en 0 |
|                       |          | en la máscara y en f las que están en f |

Ejemplo: Una implementación de tolower, es decir pasar a letras minúsculas.
Considerando que el rango A..Z está representado en el rango 0x41..0x5A (en binario 010xxxxx) y que el rango a..z corresponde a 0x61..0x7A (011xxxxx), entonces podemos escribir:


<code>
  int tolower(int c) {
    if (c>='A' && c<='Z')
      c |= 0x20; /* 010xxxxx -> 011xxxxx */
    return c;
  }
</code>

**Observación**: en realidad sería más claro escribir ''c= c-'A'+'a';'' pero el punto en este ejercicio es usar
el operador |.

===== Desplazamientos =====

El desplazamiento a la izquierda se puede usar para multiplicar eficientemente por una potencia de 2.  Por ejemplo ''x %%<<%% 4'' corresponde a multiplicar por 2<sup>4</sup>, es decir multiplicar por 16.  La ventaja es que la latencia es de un solo ciclo del reloj comparado con unos 3 ciclos si se usa la multiplicación.  Un problema es que C no especifica qué sucede si se desplaza en un número de bits igual o superior al tamaño en bits del argumento.  Por ejemplo si x es un int, se esperaría que ''x%%<<%%32'' fuese 0, pero esto no es cierto en una x86.  En otra plataformas sí puede ser 0.

El desplazamiento a la derecha se puede usar para dividir eficientemente por una potencia de 2.  Por ejemplo ''x %%>>%% 4'' corresponde a dividir por 16.  Aquí la diferencia en velocidad es mucho más importante: 1 ciclo versus muchos ciclos para una división.  Aquí hay que tener cuidado con los valores negativos.  ¿Cuanto debería ser %%-2 >> 1%%?  Uno esperaría que fuese -1, dado que se está dividiendo por 2.  Y en realidad sí lo es.

La duda se produce porque si uno desplaza -2 en 1 bit hacia la derecha rellenando con un 0 a la izquierda, el resultado pasa a ser positivo, lo que no daría -1.  La explicación de por qué no sucede esto está en que cuando se usa un desplazamiento a la derecha de un entero con signo, no se rellena con 0, si no que con el bit de signo.  En el caso de %%-2 >> 1%%, el bit de signo es 1 por lo que se rellena a la izquierda con un 1, preservando el signo negativo, y dando por lo tanto el resultado correcto -1.

Entonces cuando el tipo de la expresión a desplazar a la derecha es unsigned, entonces siempre se rellena con 0s a la izquierda.  Si es signed (con signo) se rellena con el bit de signo para preservar el signo del resultado.  En los desplazamientos a la izquierda siempre se rellena con 0s a la derecha.  En resumen, dado un entero x formado por x<sub>0</sub> x<sub>1</sub> x<sub>2</sub> ... x<sub>30</sub> x<sub>31</sub>, éstos serían los posibles resultados de desplazar x en un solo bit:

^ tipo operando ^ operación ^ resultado ^
| con o sin signo | %%x << 1%% | x<sub>1</sub> x<sub>2</sub> x<sub>3</sub> ...  x<sub>30</sub> x<sub>31</sub> 0 |
| sin signo       | %%x >> 1%% | 0 x<sub>0</sub> x<sub>1</sub> ...  x<sub>29</sub> x<sub>30</sub> |
| con signo       | %%x >> 1%% | x<sub>0</sub> x<sub>0</sub> x<sub>1</sub> ...  x<sub>29</sub> x<sub>30</sub> |

===== Ejemplo 1: conjuntos con mapas de bits =====

<code>
#include <stdio.h>

typedef enum fruta { manzana, pera, guinda, durazno, damasco } Fruta;

char *nombre_fruta[ ]= { "manzana", "pera", "guinda", "durazno", "damasco" };

typedef int Conjunto;

Conjunto singleton(Fruta f) {
  return 1<<f;
}

Conjunto Union(Conjunto r, Conjunto s) {
  return r | s;
}

Conjunto agregar(Fruta f, Conjunto s) {
  return Union(s, singleton(f));
}

int pertenece(Conjunto s, Fruta f) {
  return s & singleton(f);
}

Conjunto complemento(Conjunto s) {
  return ~s;
}
 
void mostrar(Conjunto s) {
  Fruta f; 
  for (f= manzana; f<= damasco; f++) {
    char *name;
    if (pertenece(s, f))
      printf("%s ", nombre_fruta[f]);
  }
  printf("\n");
}

int main() {
  Conjunto s1= agregar(manzana, agregar(guinda, singleton(damasco)));
  Conjunto s2= complemento(s1);

  mostrar(s1);
  mostrar(s2);
}
</code>

=== Ejercicios ===

  * Defina una nueva operación para la intersección de conjuntos
  * Defina otra operación para la diferencia de conjuntos

===== Ejemplo 2: extracción de bits =====

Supongamos que un entero sin signo x está formado por x<sub>0</sub> x<sub>1</sub> x<sub>2</sub> ... x<sub>30</sub> x<sub>31</sub>.  Por razones de eficiencia de uso de la memoria se han colocado varios enteros de pequeño tamaño en el entero x.  Por ejemplo, un entero podría estar codificado en los 12 bits ubicados en x<sub>8</sub> ... x<sub>19</sub>.  Entonces se necesita programar la función extract(x, i, k) que entrega los bits x<sub>i</sub> ... x<sub>i+k-1</sub> de x, con %%0<=i<=31%% y %%0<k<=32-i%%.  Por ejemplo extract(0x**0**48b6048, 0, 4) es 0 y extract(0x04**8b6**048, 8, 12) es 0x8b6.

Como etapa previa necesitaremos de una función que entregue una máscara con los j bits menos significativos en 1.  Por ejemplo si j=4 la máscara sería 00...001111.  Una forma errada de hacerlo sería calculando ''%%(1<<j)-1%%''.  El problema es que esto no funcionaría en x86 si j=32 porque en este procesador %%1<<32%% es 1, no 0 como uno esperaría.  Por lo tanto se debe considerar como un caso de borde.  Esta sería la función:

<code>
unsigned mascara(unsigned j) {
  return j==32 ? -1 : (1<<j)-1;
}
</code>

Para aislar los k bits de x a partir de la i-ésima posición primero se necesita borrar de x los bits x<sub>0</sub> ... x<sub>i-1</sub>.  Esto se logra de 2 maneras:

  * desplazando x en i bits a la izquierda y luego en i bits a la derecha nuevamente: %%(x << i) >> i%%
  * o con una máscara: ''x & mascara(32-i)''

Luego hay que desplazar los bits resultantes a la posición menos significativa.  Esto se logra desplazando en 32-i-k hacia la derecha, es decir calculando x >> (32-i-k).  Esto borra automáticamente los bits x<sub>i+k</sub> ... x<sub>31</sub>.  La función queda entonces:

<code>
unsigned int extract(unsigned int x, int i, int k) {
  return (  x & mascara(32-i)  ) >> (32-i-k);
}
</code>

o también:

<code>
unsigned int extract(unsigned int x, int i, int k) {
  return (x<<i) >> (32-k);
}
</code>

y por último:

<code>
unsigned int extract(unsigned int x, int i, int k) {
  return (  x & ( ((unsigned)-1)>>i ) ) >> (32-i-k);
}
</code>

=== Ejercicio ===

Programe en el computador la parte b de la pregunta 1 del [[http://users.dcc.uchile.cl/~lmateu/CC3301/controles/c1-131.pdf|control 1 del semestre Otoño de 2013]].  Pruebe su solución con el programa test-repBits.c incluido en [[http://users.dcc.uchile.cl/~lmateu/CC3301/download/bits.zip|bits.zip]].  Para compilar siga las instrucciones que aparecen en el archivo Makefile.

===== Otros Ejercicios =====

La idea en estos ejercicios es resolverlos haciendo un manejo eficientes de bits por medio de los operadores
vistos en esta unidad.

  * Dado n retornar el número de bits en 1 que tiene n: ''int bits1(int n)''
  * Retornar el número de bits de los int en esta arquitectura: ''int int_size()''
  * Dado n, poner en 0 el bit en 1 que se encuentra en posición de mayor significancia: ''int unset1(int n)''.  Ejemplo de uso:

         unset1(0x70); /* debe retornar 0x30 */
         unset1(0); /* debe retornar 0 */
         unset1(1); /* debe retornar 0 */

  * Implementar la función rotate que es un shift pero en que el bit que sale por un lado entrar por el otro: ''unsigned char rotate(unsigned char c, int bits)''.  Si bits es positivo debemos rotar a la derecha y si es negativo a la izquierda.
  * Usando solo operaciones de bits, implemente las siguientes funciones (no puede usar sumas, restas, multiplicaciones, <, >, etc):
    * int minus(int x): entrega -x
    * int is_neg(int x): entrega 1 si x<0, 0 en caso contrario.
    * int abs(int x): entrega el valor absoluto de x
  * La parte a de la pregunta 1 del [[http://users.dcc.uchile.cl/~lmateu/CC3301/controles/c1-131.pdf|control 1 del semestre Otoño de 2013]].