c - bitwise operators python

Pregunta K & R: ¿Necesita ayuda para entender el método "getbits()" en el Capítulo 2?

Question

Como mencioné antes, estoy revisando K & R, y en general estoy bien. Sin embargo, 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, y como resultado, tengo problemas con los ejercicios asociados.

(Esto no es una tontería de mi pregunta anterior sobre el cambio de bit, por cierto. ¡Esto es nuevo y mejorado!)

Así que aquí está el método provisto:

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 n bits comenzando en la posición p , contando desde la derecha (con el bit más alejado a la derecha 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;
}

El resultado 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.

(Tenga en cuenta que no estoy buscando ayuda con los ejercicios asociados, creo que si "tengo" esto, podré obtenerlos).

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

¿Alguna ayuda?

Answer 1

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 << n)

para cualquier bit establecido (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 sizeof int independent, 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. La máquina de 64 bits representaría 64 bits o 0x0000000000000000

Ahora aplique "no" (~ 0) y obtenga 11111111
desplazar a la derecha (<<) por ny obtener 11111000
y "no" eso y obtén 00000111

entonces 10010011 y 00000111 = 00000011
¿Recuerdas cómo funcionan las operaciones booleanas?

Answer 2

Yo 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 una int sin signo de 8 bits.

1. Nuestro número es 75, queremos los 4 bits comenzando desde 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 tiene 4 bits de longitud comenzando con el bit de orden más bajo, esto se hace como tal.

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

De acuerdo, tenemos nuestra máscara.

4. Ahora, empujamos los bits que queremos fuera del número en los bits de orden más bajo, así que cambiamos 75 binarios 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 del número original en el orden bajo.

4. entonces nosotros y ellos
   

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

entonces la respuesta es decimal 9.

Nota: el mordisco de orden superior resulta ser cero, 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.

Answer 3

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

1111111111111111

Cuando nos desplazamos hacia la izquierda en n bits (3 en su caso), obtenemos:

1111111111111000

porque los 1 s de la izquierda se descartan y 0 s se introducen a la derecha. Luego, al volver a complementarlo se obtiene:

0000000000000111

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

El "x bit" que describes ha desplazado el número dado (f994) hacia la derecha lo suficiente para que los 3 bits menos significativos sean los que deseas. En este ejemplo, los bits que está solicitando están rodeados por ''.'' caracteres.

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 !!

Answer 4

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

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

ANDing 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 para siempre: AnalogX PCalc .

Answer 5

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

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

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

El resultado de E1 << E2 es E1 posiciones de bit E2 desplazadas a la izquierda; los bits vacíos se rellenan con ceros. [...] Si E1 tiene un tipo firmado y un valor no negativo, y E1 × 2 E2 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 desarrollada por K & R, ingenuamente desplazando 1 bit de la izquierda al realizar el desplazamiento hacia la izquierda de un número firmado (y este código también se basa en la representación de complemento de 2), pero los sistemas no comparten esas propiedades, por lo que el proceso de estandarización C no definió este comportamiento.

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