¿Por qué -INT_MIN = INT_MIN en una representación de complemento con dos signos?

Todavía no he encontrado una razón por la cual el número negativo más bajo firmado no tiene un número positivo con signo equivalente? Quiero decir en un número binario de 3 dígitos por simplicidad 100 es -4? pero no podemos tener un 4 positivo en el formato firmado porque no podemos. Se desborda. Entonces, ¿cómo sabemos que el complemento de dos 1000 es -4 1000 0000 es -128 y así sucesivamente? No tenemos un número positivo original

Una forma de pensarlo es que el formato de complemento firmado, dos asignando cada bit una potencia de dos, y luego volteando el signo de la última potencia de dos. Miremos -4, por ejemplo, que se representa como 100. Esto significa que el valor es

-1 x 2^2 + 0 x 2^1 + 0 x 2^0 

Si queremos obtener la versión positiva de este valor, tendríamos que negarlo para obtener

  1 x 2^2 - 0 x 2^1 - 0 x 2^0 

Tenga en cuenta que este valor es igual a

  1 x 2^2 + 0 x 2^1 + 0 x 2^0 

En otras palabras, la representación binaria normal de este valor es 100. Sin embargo, tenemos problemas aquí, porque estamos usando una representación de complemento de dos firmado, lo que significa que hemos reservado específicamente el bit 4 como el bit de signo. En consecuencia, cuando tratamos de interpretar el patrón de bits 100 como un valor de complemento firmado, de tres bits y dos, se devuelve de manera idéntica a lo que comenzamos. La escasez de bits es lo que está doliendo aquí.

De manera más general, dados n bits, de los cuales el primero es el bit de signo en una representación complementaria de dos, intentar calcular -1000 … 00 devolverá el mismo valor, porque el bit necesario para almacenar el valor positivo grande tiene el valor especial significado asignado a ella.

Entonces, ¿por qué hacer esto? La razón de esto es que si solo tiene n bits, no puede almacenar los valores -2 n – 1 a 2 n – 1 , porque hay 2 n + 1 números diferentes aquí y solo 2 ^ n patrones de bits diferentes. Excluyendo el número positivo más grande, así es posible mantener todos los números diferentes en el patrón de bits especificado.

¿Pero por qué soltar el alto valor y no el bajo valor? Esto es para preservar la compatibilidad binaria con enteros sin signo. En un entero sin signo, los valores 0 a 2 n-1 – 1 están codificados utilizando la representación estándar de base dos. En consecuencia, para los enteros sin signo y con signo para aceptar en absoluto, los enteros sin signo están diseñados para que sean bit por bit equivalentes con los primeros 2 n – 1 enteros sin signo, que van de 0 a 2 n – 1 – 1, inclusive . Después de esto, los valores sin firmar necesitan el bit más significativo para codificar números, pero los valores firmados lo usan como el bit de signo.

¡Espero que esto ayude!

-INT_MIN es un desbordamiento de entero y es un comportamiento indefinido en C.

-INT_MIN garantiza que será igual a INT_MIN solo cuando el entero con signo se desborde. Esto se puede habilitar con gcc por ejemplo, con la opción -fwrapv .

El comstackdor usualmente aprovecha el hecho de que el desbordamiento de enteros es un comportamiento indefinido en C para realizar algunas optimizaciones. Depender de los desbordamientos de enteros con signo que envuelve no es seguro.

Un ejemplo bien conocido de optimización del comstackdor es el siguiente

 #define ABS(x) ((x) > 0 ? (x) : -(x)) void foo(int x){ if (ABS(x) >= 0) { // some code } } 

la mayoría de los comstackdores actuales ( gcc , icc ) con las opciones de optimización habilitadas optimizarían la prueba basándose en el hecho de que -INT_MIN es un comportamiento indefinido.

R. Hay un número par de posibilidades para el número binario de n dígitos, por lo que no podemos representar el mismo rango para números positivos y negativos.

B. Queremos que cada número que comience con 1 sea negativo, y cada número que comience con 0 no sea negativo. (No es lo contrario, porque queremos que el mismo represente positivo y cero en el firmado y el no vinculado. Por eso, 0 está en la mitad de los positivos, por lo que tienen un lugar menos.

La alternativa al complemento de dos tiene tal propiedad, se conoce como complemento de uno .
En la forma de complemento, el valor más bajo posible también tiene una forma positiva válida.


El complemento de uno funciona simplemente invirtiendo todos los bits en el número mismo.
Por ejemplo, sabemos que 0110 == 6 y en un complemento 1001 == -6 . Usando el complemento de uno, tenemos tantos números positivos como números negativos.

Pero, ¿qué pasa con la representación de bit 1111 ? Solo mirándolo, podemos decir que es la forma “negativa” de cero ( 0000 = 0; 1111 = -0 ), pero tal número no tiene ningún sentido y es algo derrochador.

En cambio, usamos complemento de dos, que es similar al complemento de uno, pero después de invertir los bits, agregamos uno. Entonces, si sabemos que 0110 = 6 , entonces el complemento de uno es 1001 y el complemento de dos es 1001 + 1 == 1010 . Usando el complemento de dos, no tenemos un “cero negativo” porque causa un desbordamiento.

Una forma diferente de verlo es “si se establece el bit más alto, entonces el número es negativo”. Eso significa que el rango positivo es [0 .. 2^(bits - 1)] y el rango negativo es todo lo demás. Hay la misma cantidad de números positivos que números negativos, pero como (en este formato) el cero se considera positivo, el rango negativo se desplaza uno a [-1 .. (neg) 2^(bits - 1)] .


Supongamos que estamos tratando con un número firmado de 3 bits en complemento a dos. Eso nos daría la siguiente tabla:

 BITS VALUE 000 0 001 1 010 2 011 3 100 -4 101 -3 110 -2 111 -1 

Puedes ver que hay la misma cantidad de números positivos que números negativos, es solo que los números negativos no comienzan desde 0 como lo hace el conjunto positivo.

El dígito faltante es 0 . En un sentido matemático, 0 no es ni positivo ni negativo. Pero en un sentido binario, dado que 0 no tiene un bit negativo, se considera positivo. En otras palabras, si quería -128 a 128, no podría haber un 0.

Porque tiene que contar 0. El rango entero [-4, -1] (o, equivalentemente -4, -3, -2 y -1) contiene 4 números y el rest del rango [0,3] (o, equivalentemente 0, 1, 2 y 3) contiene 4 números, para un total de 8, y números binarios de 3 dígitos tienen 2 a la potencia de 3 (= 8) combinaciones posibles.

Piénsalo de esta manera. Cualquier rango entero de la forma [-n, + n] necesariamente tiene un tamaño impar (2 * n + 1 enteros). Cualquier representación binaria entera que use tendrá un número diferente de números negativos y positivos porque el número de combinaciones siempre es par (potencias de 2).

Entonces, ¿cómo sabemos que el complemento de dos 1000 es -4 1000 0000 es -128 y así sucesivamente? No tenemos un número positivo original

Su error es pensar que necesitamos una representación complementaria de dos del número positivo para calcular la representación complementaria de dos del número negativo.

El proceso para encontrar el complemento de dos de un número negativo es:

Comience con la representación del complemento normal, que no sea dos, del valor absoluto del número que se representará. Entonces, para -4, tome la representación complementaria de no dos de | -4 |, 100.

Voltee todos los bits: 100 -> 011 (o … 11111011 con los que continúan indefinidamente a la izquierda).

Agregue uno: 011 -> 100 (o … 11111100)

Ahora trunca al número de bits que estás utilizando (esto elimina el bit de acarreo o la cadena infinita de 1s). Como resultado, 100 es la representación de complemento de dos y tres bits de -4.

Para ir por el otro lado, tome la representación de complemento de los dos (100) voltee los bits (011) y agregue uno (100) ahora tiene la representación complementaria de no dos de | -4 | 1 * 2 ^ 2 + 0 * 2 ^ 1 + 0 * 2 ^ 0 = 4. Por lo tanto, sabemos que la representación con la que comenzamos, 100, es la representación de complemento de 3 bits de 3.

    Intereting Posts