Diferencias

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

--- bits [2014/08/06 16:18] – lmateu
+++ bits [2018/03/22 12:57] (actual) – [Ejemplo 2: extracción de bits] lmateu
@@ Línea 1: / Línea 1: @@
 ====== Operaciones con bits ======
-===== Representación de números en binario =====
-(Esta sección se borrará de esta página porque se movió al sistema de tipos.)
-Los enteros se almacenan internamente en binario. Por ejemplo:
-(2001)<sub>10</sub> = (111 1101 0001)<sub>2</sub>
-= 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 =====
@@ Línea 45: / Línea 20: @@
   * 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 76: / Línea 51: @@
 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.
+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.  Si 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>.
+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 ^
@@ Línea 142: / Línea 117: @@
 ===== 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 i) {
+unsigned mascara(unsigned j) {
-  return i==32 ? -1 : (1<<i)-1;
+  return j==32 ? -1 : (1<<j)-1;
 }
 </code>
@@ Línea 170: / 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>