¿Por qué abs(0x80000000) == 0x80000000?

Acabo de empezar a leer Hacker’s Delight y define abs(-2³¹) como -2³¹. ¿Porqué es eso?

Lo intenté printf("%x", abs(0x80000000)) en algunos sistemas diferentes y obtengo 0x80000000 en todos ellos.

En realidad, en C, el comportamiento no está definido. Del estándar C99, §7.20.6.1/2:

los abs, labsy llabs funciones calculan el valor absoluto de un entero j. Si el resultado no se puede representar, el comportamiento no está definido.

y su nota al pie:

El valor absoluto del número más negativo no se puede representar en complemento a dos.

Para un tipo de datos de 32 bits no hay expresión de +2^31, porque el número más grande es 2^31-1… lea más sobre el complemento a dos …

Debido a que los números enteros se almacenan en la memoria como un número binario en complemento a dos, la versión positiva del valor mínimo se desborda y vuelve a ser negativa.

Es decir (en .NET, pero aún aplica):

int.MaxValue + 1 == int.MinValue  // Due to overflow.

Y

Math.Abs((long)int.MinValue) == (long)int.MaxValue + 1

Obviamente, matemáticamente, |−2³¹| es 2³¹. Si tenemos 32 bits para representar números enteros, podemos representar como máximo 2³² números. Si queremos una representación que sea simétrica alrededor de 0, tenemos que tomar algunas decisiones.

Para lo siguiente, como en su pregunta, asumo números de 32 bits de ancho. Se debe usar al menos un patrón de bits para 0. Eso nos deja con 2³²−1 o menos patrones de bits para el resto de los números. Este número es impar, por lo que podemos tener una representación que no sea exactamente simétrica con respecto a cero, o tener un número representado con dos representaciones diferentes.

• si usamos signo-magnitud representación, el bit más significativo representa el signo de un número, y el resto de los bits representan la magnitud del número. En este esquema, 0x80000000 es “cero negativo” (es decir, cero), y 0x00000000 es “cero positivo” o cero regular. En este esquema, el número más positivo es 0x7fffffff (2147483647) y el número más negativo es 0xffffffff (−2147483647). Este esquema tiene la ventaja de que es fácil de “decodificar”, y que es simétrico. Este esquema tiene la desventaja de que calcular a + b cuando a y b son de diferentes signos es un caso especial, y tiene que ser tratado de manera especial.
• Si usamos un complemento de uno representación, el bit más significativo sigue representando el signo. Los números positivos tienen ese bit como 0, y el resto de los bits constituyen la magnitud del número. Para números negativos, simplemente invierte los bits de la representación del número positivo correspondiente (toma un complemento con una larga serie de unos, de ahí el nombre complemento de unos). En este esquema, el número positivo máximo sigue siendo 0x7fffffff (2147483647), y el número negativo máximo es 0x80000000 (−2147483647). De nuevo hay dos representaciones de 0: el cero positivo es 0x00000000 y el cero negativo es 0xffffffff. Este esquema también tiene problemas con los cálculos que involucran números negativos.
• Si usamos un complemento a dos esquema, los números negativos se obtienen tomando la representación del complemento de uno y sumando 1 lo. En este esquema, solo hay un 0, a saber 0x00000000. El número más positivo es 0x7fffffff (2147483647) y el número más negativo es 0x80000000 (−2147483648). Hay una asimetría en esta representación. La ventaja de este esquema es que uno no tiene que lidiar con casos especiales para números negativos. La representación se encarga de darte la respuesta correcta siempre que el resultado no se desborde. Por esta razón, la mayor parte del hardware actual representa números enteros en esta representación.

En la representación en complemento a dos, no hay manera de representar 2³¹. De hecho, si miras tu compilador limits.h o un archivo equivalente, es posible que vea una definición para INT_MIN de tal manera:

#define INT_MIN (-2147483647 - 1)

Esto hecho en lugar de

#define INT_MIN -2147483648

porque 2147483648 es demasiado grande para caber en un int en una representación de complemento a dos de 32 bits. En el momento en que el operador menos unario “obtiene” el número para operar, ya es demasiado tarde: ya se ha producido un desbordamiento y no puede solucionarlo.

Entonces, para responder a su pregunta original, el valor absoluto del número más negativo en una representación de complemento a dos no se puede representar en esa codificación. Además, de lo anterior, para pasar de un valor negativo a un valor positivo en la representación de complemento a dos, se toma su complemento a unos y luego se suma 1. Entonces, para 0x80000000:

1000 0000 0000 0000 0000 0000 0000 0000   original number
0111 1111 1111 1111 1111 1111 1111 1111   ones' complement
1000 0000 0000 0000 0000 0000 0000 0000   + 1

recuperas el número original.

Esto se remonta a cómo se almacenan los números.

Los números negativos se almacenan usando el complemento a dos. El algoritmo va como…

Voltee todos los bits, luego agregue 1.

Usando números de ocho bits para ejemplos…

+0 = -0

00000000 -> 11111111, 11111111 + 1 = 100000000

(pero debido a la limitación de bits, esto se convierte en 00000000).

Y…

-128 [aka -(2^7)] es igual a -(-128)

10000000 -> 01111111, 01111111 + 1 = 10000000

Espero que esto ayude.

La representación de un número complemento a dos tiene el bit más significativo como un número negativo. 0x80000000 es 1 seguido de 31 ceros, el primer 1 representa -2^31 no 2^31. Por lo tanto, no hay forma de representar 2^31 ya que el número positivo más alto es 0x7FFFFFFF, que es 0 seguido de 31 unos, lo que equivale a 2^31-1.

abs(0x80000000) por lo tanto, no está definido en el complemento a dos, ya que es demasiado grande, por lo que la máquina simplemente se da por vencida y le da 0x80000000 nuevamente. Normalmente al menos.

creo que el camino abs funciona es comprobar primero el sign bit del número Si está claro, no hagas nada porque el número ya está +ve de lo contrario devolver el 2's complement del número en tu caso el numero es -ve y tenemos que encontrar su 2's complement. Pero el complemento a 2 de 0x80000000 pasa a ser 0x80000000 sí mismo.