Operaciones bit a bit y turnos

Tengo algunos problemas para entender cómo y por qué este código funciona de la forma en que lo hace. Mi compañero en esta tarea terminó esta parte y no puedo comunicarme con él para saber cómo y por qué funciona. He intentado algunas cosas diferentes para entenderlo, pero cualquier ayuda sería muy apreciada. Este código usa el complemento a 2 y una representación de 32 bits.

/* 
 * fitsBits - return 1 if x can be represented as an 
 *  n-bit, two's complement integer.
 *   1 <= n <= 32
 *   Examples: fitsBits(5,3) = 0, fitsBits(-4,3) = 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 15
 *   Rating: 2
 */
int fitsBits(int x, int n) {
    int r, c;
    c = 33 + ~n;
    r = !(((x << c)>>c)^x);
    return r;
}

c = 33 + ~n;

Esto calcula cuántos bits de alto orden quedan después de usar n bits de bajo orden.

((x << c)>>c

Esto llena los bits de orden superior con el mismo valor que el bit de signo de x.

!(blah ^ x)

Esto es equivalente a

blah == x

• En una plataforma de complemento a 2 -n es equivalente a ~n + 1. Por esta razón, c = 33 + ~n en dicha plataforma es en realidad equivalente a c = 32 - n. Este c tiene la intención de representar cuántos bits de orden superior quedan en un 32 bits int valor si n los bits inferiores están ocupados.

  Tenga en cuenta dos piezas de dependencia de plataforma presentes en este código: plataforma de complemento a 2, 32 bits int tipo.

• Entonces ((x << c) >> c se pretende firmar-llenar aquellas c bits de orden superior. Sign-fill significa que esos valores de x eso tiene 0 en posición de bit n - 1, estos bits de orden superior deben ponerse a cero. Pero para esos valores de x eso tiene 1 en posición de bit n - 1estos bits de orden superior deben llenarse con 1s. Esto es importante para que el código funcione correctamente para valores negativos de x.

  Esto introduce otras dos piezas de dependencia de la plataforma: << operador que se comporta bien cuando cambia valores negativos o cuando 1 se cambia al bit de signo (formalmente es un comportamiento indefinido) y >> operador que realiza la extensión de signo cuando cambia valores negativos (formalmente está definido por la implementación)

• El resto es, como se respondió anteriormente, solo una comparación con el valor original de x: !(a ^ b) es equivalente a a == b. Si las transformaciones anteriores no destruyeron el valor original de x entonces x de hecho encaja en n bits inferiores de representación en complemento a 2.

Usando el complemento bit a bit (unario ~) el operador en un entero con signo tiene aspectos definidos por la implementación e indefinidos. En otras palabras, este código no es portátil, incluso cuando considera solo implementaciones de complemento a dos.

Es importante señalar que incluso las representaciones en complemento a dos en C pueden tener representaciones trampa. 6.2.6.2p2 incluso establece esto bastante claro:

Si el bit de signo es uno, el valor se modificará de una de las siguientes formas:

— se niega el valor correspondiente con el bit de signo 0 (signo y magnitud);

— el bit de signo tiene el valor -(2 M ) (complemento a dos);

— el bit de signo tiene el valor -(2 M – 1) (complemento a uno).

Cuál de estos se aplica está definido por la implementación, como es si el valor con bit de signo 1 y todos los bits de valor cero (para los dos primeros)o con bit de signo y todos los bits de valor 1 (para complemento de uno), es una representación trampa o un valor normal.

El énfasis es mío. El uso de representaciones de trampas es un comportamiento indefinido.

Hay implementaciones reales que reservan ese valor como una representación de trampa en el modo predeterminado. El más notable que tiendo a citar es Unisys Clearpath Dordado en OS2200 (ir a 2-29). Anote la fecha en ese documento; tales implementaciones no son necesariamente antiguas (de ahí la razón por la que cito esta).

De acuerdo a 6.2.6.2p4, cambiar los valores negativos a la izquierda también es un comportamiento indefinido. No he investigado mucho sobre qué comportamientos existen en la realidad, pero esperaría razonablemente que haya implementaciones que extiendan el signo, así como implementaciones que no lo hagan. Esta sería también una forma de formar el representaciones trampa mencionados anteriormente, que son de naturaleza indefinida y, por lo tanto, indeseables. Teóricamente (o tal vez en algún momento en un futuro distante o no tan lejano), también podría enfrentar señales “correspondientes a una excepción computacional” (esa es una categoría estándar de C similar a la que SIGSEGV cae, correspondiente a cosas como “división por cero”) o comportamientos erráticos y/o indeseables…

En conclusión, la única razón por la que el código en la pregunta funciona es por coincidencia que las decisiones que tomó su implementación se alinearon de la manera correcta. Si usa la implementación que he enumerado, probablemente encontrará que este código no funciona como se esperaba para algunos valores.

Tal hechicería pesada (como se ha descrito en los comentarios) no es realmente necesario, y realmente no me parece tan óptimo. Si quieres algo que no dependa de magia (por ejemplo, algo portátil) para resolver este problema considere usar esto (en realidad, este código funcionará durante al menos 1 <= n <= 64):

#include <stdint.h>

int fits_bits(intmax_t x, unsigned int n) {
    uintmax_t min = 1ULL << (n - 1),
              max = min - 1;
    return (x < 0) * min + x <= max;
}