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

6 minutos de lectura

Necesito ayuda para entender el metodo getbits en el Capitulo
juan rudy

En el capítulo 2, la sección sobre operadores bit a bit (sección 2.9), tengo 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 Xdevolverá el norte bits que comienzan en la posición pags, contando desde la derecha (siendo el bit más a la derecha la posición 0). Dado lo siguiente main() método:

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)

Obtengo partes de esto, pero tengo problemas con el “panorama general”, principalmente debido a las partes (sin juego de palabras) que no entiendo.

La parte con la que estoy teniendo problemas específicamente es la pieza de complementos: ~(~0 << n). Creo que entiendo la primera parte, lidiando con X; es esta parte (y luego la máscara) con la que estoy luchando, y cómo todo se une para recuperar esos fragmentos. (Lo cual he verificado que está haciendo, tanto con el código como al verificar mis resultados usando calc.exe, ¡gracias a Dios que tiene una vista binaria!)

¿Alguna ayuda?

Necesito ayuda para entender el metodo getbits en el Capitulo
paxdiablo

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

1111111111111111

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

1111111111111000

porque el 1s a la izquierda se descartan y 0s se introducen a la derecha. Luego, volver a complementarlo da:

0000000000000111

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

El “bit x” que describe ha cambiado el número dado (f994 = 1111 1001 1001 0100) lo suficientemente lejos como para que los 3 bits menos significativos sean los que desea. En este ejemplo, los bits de entrada que está solicitando están ahí, todos los demás bits de entrada están marcados . ya que no son importantes para el resultado final:

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

Como puede ver, ahora tiene los bits relevantes, en las posiciones de bits más a la derecha.

  • Iba a sugerir el cambio a la derecha, para guardar una instrucción, pero supongo, ~(~0 << n) elegantemente le permite ignorar el tamaño de la palabra con la que está trabajando…

    – tontería

    1 de diciembre de 2013 a las 8:58

  • No entiendo algo, ¿dónde me equivoco? int a = 0; entonces printf(“%d”, a) da 0. Ahora, a = ~a entonces printf(“%d”, a) da -1, ¿por qué?

    – Anatoly

    8 de noviembre de 2014 a las 11:12


  • @Anatoly: es porque ~ invierte todos los bits a 1 y, en la codificación de complemento a dos, eso es -1.

    – pax diablo

    9 de noviembre de 2014 a las 2:46

  • Gran respuesta. ¡Finalmente entiendo este ejemplo! 🙂

    – Kirol

    12 de septiembre de 2018 a las 8:09

  • Gracias por esa gran respuesta @paxdiablo. Sin embargo, para comprender completamente cada paso del camino, me gustaría poder aislar cada paso. Para cuando intento imprimir printf("try: %d\n", ~0 << 1);me sale un error: printf("try: %d\n", ~0 << 1); ~~ ^ 1 warning generated. Undefined symbols for architecture x86_64: "_printnozero", referenced from: _main in getbits-923932.o ld: symbol(s) not found for architecture x86_64. Hay otra forma de imprimirlo. Si no, ¿por qué no puedo imprimirlo?

    – ecjb

    1 de febrero a las 8:35


1647558073 318 Necesito ayuda para entender el metodo getbits en el Capitulo
Ninguna

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

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

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

  2. 75 en binario es 0100 1011

  3. Entonces creamos una máscara que tiene 4 bits de largo comenzando con el bit de orden más bajo, esto se hace como tal.

~0 = 1111 1111
<<4 = 1111 0000
~ = 0000 1111

Bien, tenemos nuestra máscara.

  1. Ahora, sacamos los bits que queremos del número a los bits de orden más bajo, por lo que cambiamos el 75 binario por 6+1-4=3.

0100 1011 >>3 0000 1001

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

  1. entonces nosotros y ellos
  0000 1001 
& 0000 1111 ============ 0000 1001

entonces la respuesta es 9 decimal.

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

1647558073 970 Necesito ayuda para entender el metodo getbits en el Capitulo
david subvención

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

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

ANDing el resultado con otra cosa devolverá lo que hay en esos n pedacitos

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

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

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

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

El resultado de E1 << E2 es E1 desplazado a la izquierda E2 posiciones de bits; los bits vacíos se rellenan con ceros. […] Si E1 tiene un tipo con signo y un valor no negativo, y E1 × 2E2 es representable en el tipo de resultado, entonces ese es el valor resultante; de lo contrario, el comportamiento no está definido.

En K&R C, este código se habría basado en la clase particular de sistema que desarrolló K&R, cambiando ingenuamente 1 bits a la izquierda cuando se realiza 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 a 2), pero algunos otros sistemas no comparten esas propiedades, por lo que el proceso de estandarización de C no definió este comportamiento.

Entonces, este ejemplo solo es interesante como curiosidad histórica, no debe usarse en ningún código real desde 1989 (si no antes).

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

y centrándonos en este conjunto de operaciones ~(~0 << n)

para cualquier conjunto de bits (10010011, etc.), desea generar una “máscara” que extraiga solo los bits que desea ver. Entonces 10010011 o 0x03, estoy interesado en xxxxx011. ¿Cuál es la máscara que extraerá ese conjunto? 00000111 Ahora quiero ser independiente del tamaño de int, dejaré que la máquina haga el trabajo, es decir, comenzar con 0 para una máquina de bytes, es 0x00 para una máquina de palabras, es 0x0000, etc.

Ahora aplique “no” (~0) y obtenga 11111111
desplazar a la derecha (<<) por n y obtener 11111000
y “no” eso y obtener 00000111

entonces 10010011 y 00000111 = 00000011

¿Recuerdas cómo funcionan las operaciones booleanas?

  • @jim: Oye, no menospreciando la precisión de tu publicación. En cuanto al contenido, tiene más para continuar que cualquiera de los otros dos, sería bueno usar bloques de código y alinear los cambios. Las publicaciones usan el marcado wiki y una página de tute se vincula con el “?” encima del cuadro de respuesta. Tuve que leerlo dos veces para poder comprobarlo.

    –Ande Turner

    13 de octubre de 2008 a las 14:20

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

// la publicación sobre el desplazamiento a la izquierda que causa un problema es incorrecta.

carácter sin firmar m,l;

m = ~0 >> 4; está produciendo 255 y es igual a ~0 pero,

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

metro = 255 >> 4;

no hay problema con el desplazamiento a la izquierda negativo ~0 << lo que

  • @jim: Oye, no menospreciando la precisión de tu publicación. En cuanto al contenido, tiene más para continuar que cualquiera de los otros dos, sería bueno usar bloques de código y alinear los cambios. Las publicaciones usan el marcado wiki y una página de tute se vincula con el “?” encima del cuadro de respuesta. Tuve que leerlo dos veces para poder comprobarlo.

    –Ande Turner

    13 de octubre de 2008 a las 14:20

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad