Necesita ayuda para entender el método" getbits () " en el Capítulo 2 de K & R C

En el capítulo 2, la sección sobre operadores bitwise (sección 2.9), estoy teniendo problemas para entender cómo funciona uno de los métodos de muestra.

Aquí está el método proporcionado: 

unsigned int getbits(unsigned int x, int p, int n) {
    return (x >> (p + 1 - n)) & ~(~0 << n);
}

La idea es que, para el número dado x, devolverá los bits n comenzando en la posición p, contando desde la derecha (con el bit derecho más lejano siendo la posición 0). Dado el siguiente método main(): 

int main(void) {
    int x = 0xF994, p = 4, n = 3;
    int z = getbits(x, p, n);
    printf("getbits(%u (%x), %d, %d) = %u (%X)\n", x, x, p, n, z, z);

    return 0;
}

La salida es:

getbits(63892 (f994), 4, 3) = 5 (5)

Recibo porciones de esto, pero estoy teniendo problemas con el "panorama general", principalmente debido a los bits (sin juego de palabras) que no entiendo.

La parte con la que específicamente tengo problemas es la pieza de complementos: ~(~0 << n). Creo que tengo la primera parte, tratando con x ; es esta parte (y luego la máscara) con la que estoy luchando -- y cómo todo se une para recuperar realmente esos bits. (Que he verificado que está haciendo, tanto con el código y comprobando mis resultados usando calc.exe thank gracias a Dios que tiene una vista binaria!)

Alguna ayuda?

Author: Gaurang Tandon, 2008-10-13
Source

6 answers

Usemos 16 bits para nuestro ejemplo. En ese caso, ~0 es igual a 

1111111111111111

Cuando cambiamos a la izquierda este n bits (3 en su caso), obtenemos: 

1111111111111000

Porque los 1 s a la izquierda se descartan y los 0 s se alimentan a la derecha. A continuación, re-complementarlo da: 

0000000000000111

Así que es solo una forma inteligente de obtener n 1 bits en la parte menos significativa del número.

El "bit x" que describe ha desplazado el número dado (f994) lo suficientemente lejos como para que el menor significativo 3 bits son los que desea. En este ejemplo, los bits que estás solicitando están rodeados por '.' caracter.

ff94             11111111100.101.00  # original number
>> p+1-n     [2] 0011111111100.101.  # shift desired bits to right
& ~(~0 << n) [7] 0000000000000.101.  # clear all the other (left) bits

Y ahí tienes tus partes. Ta da !!

 34
Author: paxdiablo,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2010-01-05 13:03:38

Yo diría que lo mejor es hacer un problema a mano, de esa manera entenderás cómo funciona.

Esto es lo que hice usando un int sin signo de 8 bits.

  1. Nuestro número es 75 queremos los 4 bits a partir de la posición 6. la llamada para la función sería getbits(75,6,4);

  2. 75 en binario es 0100 1011

  3. Así que creamos una máscara que es de 4 bits de largo a partir del bit de orden más bajo esto se hace como tal.

~0 = 1111 1111
~ = 0000 1111

Bien, tenemos nuestra máscara.

  1. Ahora, empujamos los bits que queremos fuera del número en los bits de orden más bajo para cambiamos binario 75 por 6 + 1-4 = 3.

0100 1011 >>3 0000 1001

Ahora tenemos una máscara del número correcto de bits en el orden bajo y los bits que queremos fuera del número original en el orden bajo.

  1. así que nosotros y ellos
  0000 1001 

& 0000 1111
============

  0000 1001

Así que la respuesta es decimal 9.

Nota: el nibble de orden superior resulta ser todos los ceros, haciendo que el enmascaramiento sea redundante en este caso, pero podría haber sido cualquier cosa dependiendo del valor del número con el que empezamos.

 11
Author: None,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2008-10-13 15:31:35

~(~0 << n) crea una máscara que tendrá los bits n más a la derecha activados.

0
   0000000000000000
~0
   1111111111111111
~0 << 4
   1111111111110000
~(~0 << 4)
   0000000000001111

Y el resultado con algo más devolverá lo que hay en esos n bits.

Editar: Quería señalar la calculadora de este programador que he estado usando desde siempre: AnalogX PCalc .

 6
Author: David Grant,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2013-11-01 23:29:25

Nadie lo mencionó todavía, pero en ANSI C ~0 << n causa un comportamiento indefinido.

Esto se debe a que ~0 es un número negativo y los números negativos que cambian a la izquierda no están definidos.

Referencia: C11 6.5.7 / 4 (versiones anteriores tenían texto similar)

El resultado de E1 << E2 es E1 posiciones de bits cambiadas a la izquierda E2; los bits vacíos se rellenan con ceros. [...] Si E1 tiene una firma tipo y valor no negativo, y E1 × 2E2 es representable en el resultado escriba, entonces ese es el valor resultante; de lo contrario, el comportamiento es indefinido.

En K&R C este código se habría basado en la clase particular de sistema en la que K&R desarrolló, desplazando ingenuamente 1 bits de la izquierda al realizar el desplazamiento a la izquierda de un número con signo (y este código también se basa en la representación del complemento de 2), pero algunos otros sistemas no comparten esas propiedades, por lo que el proceso de estandarización de C no definió este comportamiento.

Así que este ejemplo es realmente solo interesante como curiosidad histórica, no debe ser utilizado en ningún código real desde 1989 (si no antes).

 3
Author: M.M,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2016-05-11 13:26:39

Usando el ejemplo: int x = 0xF994, p = 4, n = 3; int z = getbits (x, p, n);

Y centrándose en este conjunto de operaciones ~(~0

Para cualquier conjunto de bits (10010011, etc.) desea generar una "máscara" que extraiga solo los bits que desea ver. Así que 10010011 o 0x03, estoy interesado en xxxxx011. ¿Cuál es la máscara que extraerá ese conjunto ? 00000111 Ahora quiero ser sizeof int independiente, voy a dejar que la máquina hacer el trabajo es decir, empezar con 0 para una máquina de bytes es 0x00 para un máquina de la palabra es 0x0000 etc. Máquina de 64 bits podría representar por medio de 64 bits o 0x0000000000000000

Ahora aplique " not " (~0) y obtenga 11111111
cambiar a la derecha ( y" no " eso y obtener 00000111

so 10010011 & 00000111 = 00000011
¿Recuerdas cómo funcionan las operaciones booleanas ?

 2
Author: ,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2008-10-13 14:00:48

En ANSI C ~0 >> n causa un comportamiento indefinido

// la publicación sobre el desplazamiento a la izquierda que causa un problema está mal.

Unsigned char m, l;

M = ~0 > > 4; está produciendo 255 y su igual a ~0 pero,

M = ~0; l = m > > 4; está produciendo el valor correcto 15 igual que:

M = 255 >> 4;

No hay ningún problema con el desplazamiento izquierdo negativo ~0 << en absoluto

 -2
Author: Surfer Boy,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2018-02-23 00:53:47