Valor absoluto abs (x) usando operadores bit a bit y lógica booleana

Solución:

Suponiendo palabras de 32 bits, como se indica en la pregunta:

Por negativo x, x >> 31 está definido por la implementación en los estándares C y C ++. El autor del código espera números enteros en complemento a dos y un desplazamiento aritmético a la derecha, en el que x >> 31 produce todos los bits cero si el bit de signo de x es cero y todos los bits de uno si el bit de signo es uno.

Por tanto, si x es positivo o cero, y es cero, y x + y es x, asi que (x + y) ^ y es x, que es el valor absoluto de x.

Si x es negativo, y son todos unos, lo que representa −1 en complemento a dos. Luego x + y es x - 1. Luego, XORing con todos unos invierte todos los bits. Invertir todos los bits equivale a tomar el complemento a dos y restar uno, y el complemento a dos es el método utilizado para negar enteros en formato de complemento a dos. En otras palabras, XORing q con todos da -q - 1. Entonces x - 1 XORed con todos produce -(x - 1) - 1 = -x + 1 - 1 = -x, que es el valor absoluto de x excepto cuando x es el valor mínimo posible para el formato (−2,147,483,648 para el complemento a dos de 32 bits), en cuyo caso el valor absoluto (2,147,483,648) es demasiado grande para representarlo, y el patrón de bits resultante es solo el original x.

Este enfoque se basa en muchos comportamientos específicos de implementación:

1. Asume que x tiene 32 bits de ancho. Aunque, podrías arreglar esto x >> (sizeof(x) * CHAR_BIT - 1)
2. Supone que la máquina utiliza la representación en complemento a dos.
3. el operador de desplazamiento a la derecha copia el bit de signo de izquierda a derecha.

Ejemplo con 3 bits:

101 -> x = -3
111 -> x >> 2

101 + 111 = 100 -> x + y

100 XOR 111 -> 011 -> 3

Esto no es portátil.

Esto no es portátil, pero explicaré por qué funciona de todos modos.

La primera operación explota un rasgo de números negativos en complemento a 2, que el primer bit es 1 si es negativo y 0 si es positivo. Esto se debe a que los números van desde

El siguiente ejemplo es para 8 bits, pero se puede extrapolar a cualquier número de bits. En su caso, son 32 bits (pero 8 bits muestran los rangos más fácilmente)

10000000 (smallest negative number)
10000001 (next to smallest)
...
11111111 (negative one)
00000000 (zero)
00000001 (one)
...
01111110 (next to largest)
01111111 (largest)

Las razones para usar la codificación de números en complemento a 2 se deben a la propiedad de que agregar cualquier número negativo a su número positivo da como resultado cero.

Ahora, para crear el negativo de un número en complemento a 2, necesitarías

1. Tome la inversa (no bit a bit) de un número de entrada.
2. Agrégale uno.

La razón por la que se le agrega el 1 es para forzar la característica de la adición a poner a cero el registro. Verá, si solo fuera x + ~ (x), entonces obtendría un registro de todos los 1. Al agregarle uno, se obtiene un acarreo en cascada que produce un registro de ceros (con un 1 en el acarreo del registro).

Esta comprensión es importante para saber “por qué” funciona (principalmente) el algoritmo que proporcionó.

y = x >> 31   // this line acts like an "if" statement.
              // Depending on if y is 32 signed or unsigned, when x is negative, 
              // it will fill y with 0xFFFFFFFF or 1.  The rest of the 
              // algorithm doesn't, care because it accommodates both inputs.
              // when x is positive, the result is zero.

Exploraremos (x es positivo primero)

(x + y) ^ y   // for positive x, first we substitute the y = 0
(x + 0) ^ 0   // reduce the addition
(x) ^ 0       // remove the parenthesis
x ^ 0         // which, by definition of xor, can only yield x
x

Ahora exploremos (x es negativo, y es 0xFFFFFFFF (y estaba firmado))

(x + y) ^ y   // first substitute the Y
(x + 0xFFFFFFFF) ^ 0xFFFFFFFF // note that 0xFFFFF is the same as 2's complement -1
(x - 1) ^ 0xFFFFFFFF // add in a new variable Z to hold the result
(x - 1) ^ 0xFFFFFFFF = Z  // take the ^ 0xFFFFFFFF of both sides
(x - 1) ^ 0xFFFFFFFF ^ 0xFFFFFFFF = Z ^ 0xFFFFFFFF // reduce the left side
(x - 1) = z ^ 0xFFFFFFFF // note that not is equivalent to ^ 0xFFFFFFFF
(x - 1) = ~(z) // add one to both sides
x - 1 + 1 = ~(z) + 1 //  reduce
x = ~(z) + 1  // by definition z is negative x (for 2's complement numbers)

Ahora exploremos (x es negativo, y es 0x01 (y no estaba firmado))

(x + y) ^ y   // first substitute the Y
(x + 1) ^ 0x00000001 // note that x is a 2's complement negative, but is
                     // being treated as unsigned, so to make the unsigned
                     // context of x tracable, I'll add a -(x) around the X
(-(x) + 1) ^ 0x00000001 // which simplifies to
(-(x - 1)) ^ 0x00000001 // negative of a negative is positive
(-(x - 1)) ^ -(-(0x00000001)) // substituting 1 for bits of -1
(-(x - 1)) ^ -(0xFFFFFFFF) // pulling out the negative sign
-((x-1) ^ 0xFFFFFFFF) // recalling that while we added signs and negations to
                      // make the math sensible, there's actually no place to
                      // store them in an unsigned storage system, so dropping
                      // them is acceptable
x-1 ^ 0XFFFFFFFF = Z // introducing a new variable Z, take the ^ 0xFFFFFFF of both sides
x-1 ^ 0xFFFFFFFF ^ 0xFFFFFFFF = Z ^ 0xFFFFFFFF // reduce the left side
x-1 = z ^ 0xFFFFFFFF // note that not is equivalent to ^ 0xFFFFFFFF
x-1 = ~(z) // add one to both sides
x - 1 + 1 = ~(z) + 1 //  reduce
x = ~(z) + 1  // by definition z is negative x (for 2's complement numbers, even though we used only non-2's complement types)

Tenga en cuenta que si bien las pruebas anteriores son aceptables para una explicación general, la realidad es que estas pruebas no cubren casos extremos importantes, como x = 0x80000000, que representa un número negativo mayor en valor absoluto que cualquier X positivo que podría almacenarse en el mismo número de bits.

---

---

Utiliza Nuestro Buscador