Operaciones bit a bit y turnos

2 minutos de lectura

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;
}

  • Esto es hechicería pesada. No se supone que realmente lo entiendas, solo acéptalo como sabiduría de lo alto. Sugerencia: encaja si todos los bits a la izquierda de la posición n-1 tienen el mismo valor que el bit de la posición n-1.

    –David Schwartz

    9 de febrero de 2013 a las 22:56

  • Descubrir que hace cada operador (y comprenda el complemento a 2), luego discuta qué sucedería con varios valores de entrada. Se necesita mucha práctica para poder leer fácilmente algo como lo anterior.

    – Bernhard Barker

    9 de febrero de 2013 a las 22:59


  • eso es… magnifico :O

    – Andreas Grapentin

    9 de febrero de 2013 a las 23:49

  • lindo hechizo! verdaderamente mágico

    – philx_x

    21 de septiembre de 2017 a las 15:09

avatar de usuario
Aprendiz de código

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

  • Solo por interés, me pregunto por qué no usaron (x & ~(1 << c)) en lugar de ((x >> c) << c)? Habría eliminado una dependencia intermedia, por lo que tal vez habría ahorrado uno o dos ciclos en un procesador canalizado fuera de servicio.

    – SecurityMatt

    10 de febrero de 2013 a las 0:08

  • @SecurityMatt Estoy seguro de que hay varias formas de lograr lo mismo.

    – Aprendiz de código

    10 de febrero de 2013 a las 0:43

  • @SecurityMatt: no funcionaría correctamente con entradas negativas. El propósito de (x << c) >> c no es para cero fuera los bits de orden superior (como afirma incorrectamente esta respuesta), sino más bien para firmar-llenar a ellos. Para valores negativos el relleno es 1no 0. Esto es exactamente lo que hace que este código funcione para valores negativos.

    – Ant

    30 de agosto de 2015 a las 3:14


  • @ovgolovin: funciona con valores negativos siempre que los detalles de implementación enumerados en mi respuesta estén allí. En general, esta no es una implementación portátil y, en ese sentido, no funciona con ningún valor.

    – Ant

    30 de agosto de 2015 a las 3:24


  • @Seb: Sí, pero no es solo eso. Esta implementación también se basa en algunos positivo los valores se vuelven negativos cuando su bit de orden superior se desplaza a la posición de bit de signo. Esto es fundamental para hacer que este código rechace, por ejemplo, (5, 3) aporte. Por supuesto, formalmente esto también es UB.

    – Ant

    30 de agosto de 2015 a las 5:11


avatar de usuario
Hormiga

  • 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.

avatar de usuario
autista

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;
}

  • La pregunta dice “Este código usa complemento a 2 y una representación de 32 bits”. por lo que sus objeciones no son relevantes. ~ no puede producir una representación trampa en complemento a 2 (6.2.6.2/1 nota al pie 53)

    –MM

    30 de agosto de 2015 a las 4:47


  • @MattMcNabb No use notas al pie de página informativas para contrarrestar las referencias normativas.

    – autista

    30 de agosto de 2015 a las 4:51

  • Punto justo, sin embargo, el valor con el bit de signo establecido y todos los bits de valor cero no pueden ser producidos por este código de todos modos (bajo las condiciones dadas).

    –MM

    30 de agosto de 2015 a las 4:53

  • @MattMcNabb Si continúa leyendo, puede notar que menciono el UB de cambiar los valores negativos a la izquierda … ¿Está diciendo que eso no es relevante aquí?

    – autista

    30 de agosto de 2015 a las 4:56

  • @MattMcNabb Aún así, ¿esta respuesta todavía merece un voto negativo, a pesar de plantear una preocupación que ciertamente es relevante?

    – autista

    30 de agosto de 2015 a las 4:59

¿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