Diferencias

Muestra las diferencias entre dos versiones de la página.

--- bits [2014/08/05 04:29] – [Operadores de bits] lmateu
+++ bits [2018/03/22 12:57] (actual) – [Ejemplo 2: extracción de bits] lmateu
@@ Línea 1: / Línea 1: @@
-===== Operaciones con bits =====
+====== Operaciones con bits ======
-Los enteros se almacenan internamente en binario. Por ejemplo:
-(2001)<sub>10</sub> = (111 1101 0001)<sub>2</sub>
+===== Operadores de bits =====
-= 2<sup>10</sup>+2<sup>9</sup>+2<sup>8</sup>+2<sup>7</sup>+2<sup>6</sup>+2<sup>4</sup>+2<sup>0</sup>
-= 1024+512+256+128+64+16+1
-Aunque la representación interna sea en binario, el lenguaje C permite escribir los número en notación
-decimal, octal y hexadecimal.
-Un número octal siempre comienza con un 0 y cada cifra representa 3 bits:
-(2001)<sub>10</sub> = (11 111 010 001)<sub>2</sub> = (3721)<sub>8</sub> = 03721
-¡Cuidado!  Un cero a la izquierda en C sí tiene valor, porque cambia la notación decimal por octal.
-Es decir:
-<code>int i= 010;</code> es equivalente a <code>int i= 8; </code>
-Un número en hexadecimal siempre comienza con el prefijo 0x y cada cifra representa 4 bits:
-(2001)<sub>10</sub> = (111 1101 0001)<sub>2</sub> = (7d1)<sub>16</sub> = 0x7d1
-==== Operadores de bits ====
 ^ Símbolo ^ Función ^ latencia (ciclos) ^ significado ^
@@ Línea 36: / Línea 15: @@
 reloj.
-=== Máscaras de bits ===
+===== 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 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:
@@ Línea 66: / Línea 45: @@
 el operador |.
-=== Desplazamientos ===
+===== 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 nó 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.
+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.
-=== Ejemplo 1: conjuntos con mapas de bits ===
+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>
@@ Línea 127: / Línea 115: @@
   * Defina otra operación para la diferencia de conjuntos
-=== Ejemplo 2: extracción de bits ===
+===== 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.  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%%  Por ejemplo extract(0x048b6048, 0, 4) es 0 y extract(0x048b6048, 8, 12) es 0x8b6.
+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 i bits menos significativos en 1.  Una forma errada de hacerlo sería calculando %%(1<<i)-1%%.  El problema es que esto no funcionaría en x86 si i=32.  Por lo tanto se debe considerar como un caso de borde.  Esta sería la función:
+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 k) {
+unsigned mascara(unsigned j) {
-  return k==32 ? -1 : (1<<k)-1;
+  return j==32 ? -1 : (1<<j)-1;
 }
 </code>
@@ Línea 157: / Línea 145: @@
 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>
@@ Línea 164: / Línea 160: @@
 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 ====
+===== Otros Ejercicios =====
 La idea en estos ejercicios es resolverlos haciendo un manejo eficientes de bits por medio de los operadores