math - positivo - ¿De dónde salió el 1 principal significa número negativo en int firmado?
javascript numero siempre positivo (5)
Bueno, tenía que funcionar de tal manera que 2 plus -2 da cero. Los CPUs tempranos tenían suma y resta de hardware y alguien notó que al complementar todos los bits (el complemento de uno, el sistema original), para cambiar el "signo" del valor, permitía que el hardware de adición existente funcionara correctamente, excepto que a veces el resultado fue cero negativo. (¿Cuál es la diferencia entre -0 y 0? En tales máquinas, era indeterminado.)
Alguien pronto se dio cuenta de que al usar el complemento a dos (convertir un número entre negativo y positivo al invertir los bits y agregar uno), se evitó el problema del cero negativo.
Entonces realmente, no es solo el bit de signo el que se ve afectado por los negativos, sino todos los bits excepto el LSB. Sin embargo, al examinar el MSB, uno puede determinar inmediatamente si el valor firmado allí es negativo.
Aunque he leído una serie de artículos que dicen que, en su mayoría, el complemento de 2 se usa para representar los números negativos en un entero con signo y que ese es el mejor método,
Sin embargo, por alguna razón tengo esto (a continuación) metido en mi cabeza y no puedo deshacerme de él sin conocer su historial.
"Use el bit inicial como 1 para denotar números negativos cuando use int firmado".
He leído muchos mensajes en línea y en StakOverflow que el complemento de 2 es la mejor manera de representar números negativos. Pero mi pregunta no es sobre la mejor manera, se trata de la historia o de dónde surgió el concepto del "primer bit" y luego desapareció.
PD: Tampoco soy yo, muchos otros también se confundieron con esto.
Editar - 1 El método llamado 1 principal que mencioné se describe con un ejemplo en esta publicación: ¿Por qué se usa el complemento de dos para representar números negativos?
Ahora entiendo, el MSB de 1 significa números negativos. Esto es por naturaleza del complemento de 2 y no de ningún esquema especial.
P.ej. Si no fuera por el 1er bit, no podemos decir si 1011 representa -5 o +11.
Gracias a: jamesdlin, Oli Charlesworth, Mr Lister por hacer preguntas implorantes para hacerme darme cuenta de la respuesta correcta.
Rant: creo que hay un montón de grupos / personas a quienes se les ha enseñado o se les ha hecho pensar (incorrectamente) que 1011 se evalúa a -3. 1 que denota - y 011 que denota 3.
Las personas que preguntaron "cuál era mi pregunta ..." probablemente se les enseñó el complemento correcto de 2 de la primera instancia que lo aprendieron y no se expusieron a estas respuestas incorrectas.
La representación de complementos de dos para las enteros con signo tiene varias ventajas.
Supongamos 16 bits por ahora.
Los números no negativos en el rango de 0 a 32.767 tienen la misma representación tanto en tipos firmados como sin firmar. (Two''s-complement comparte esta característica con el complemento de uno y la magnitud y signo).
Complemento de dos es fácil de implementar en hardware. Para muchas operaciones, puede usar las mismas instrucciones para la aritmética firmada y sin firmar (si no le importa ignorar el desbordamiento). Por ejemplo, -1 se representa como 1111 1111 1111 1111 , y +1 como 0000 0000 0000 0001 . Si los agrega, ignorando el hecho de que el bit de orden superior es un bit de signo, el resultado matemático es 1 0000 0000 0000 0000 ; descartando todos menos los 16 bits de orden inferior, le da 0000 0000 0000 0000 , que es el resultado correcto firmado. Interpretando la misma operación como sin signo , está agregando 65535 + 1 y obteniendo 0 , que es el resultado correcto sin signo (con el módulo envolvente 65536).
Puedes pensar en el bit adelantado, no como un "bit de signo", sino simplemente como otro bit de valor. En una representación binaria sin signo , cada bit representa 0 o 1 multiplicado por el valor de posición, y el valor total es la suma de esos productos. El valor de posición del bit más bajo es 1, el siguiente bit más bajo es 2, luego 4, etc. En una representación sin firmar de 16 bits, el valor de posición del bit de orden superior es 32768 . En una representación de complemento de dos bits de 16 bits, el valor de posición del bit de orden superior es -32768 . Prueba algunos ejemplos y verás que todo se resume bien.
Ver Wikipedia para más información.
No se trata solo del primer paso. Se trata de todos los bits.
Comenzando con la suma
Primero veamos cómo se hace la adición en el binario de 4 bits para 2 + 7:
10 +
111
____
1001
Es lo mismo que la adición larga en decimal: bit por bit, de derecha a izquierda.
- En el lugar más a la derecha, agregamos 0 y 1, hace 1, no lleva.
- En el segundo lugar desde la derecha, agregamos 1 y 1, que hace 2 en decimal o 10 en binario - escribimos el 0, llevamos el 1.
- En el tercer lugar desde la derecha, agregamos el 1 que llevamos al 1 que ya está allí, hace un binario 10. Escribimos el 0, llevamos el 1.
- El 1 que acaba de llevarse se escribe en el cuarto lugar desde la derecha.
Larga resta
Ahora sabemos que 10 + 111 binarios = 1001, deberíamos poder retroceder y demostrar que 1001 - 10 = 111. De nuevo, esto es exactamente lo mismo que en la resta larga decimal.
1001 -
10
____
111
Esto es lo que hicimos, trabajando de derecha a izquierda nuevamente:
- En el lugar más a la derecha, 1 - 0 = 1, escribimos eso.
- En segundo lugar, tenemos 0 - 1, así que tenemos que pedir prestado un poco más. Ahora hacemos binary 10 - 1, que sale 1. Escribimos esto.
- En tercer lugar, recuerda que pedimos prestado un poco más, así que de nuevo tenemos 0 - 1. Usamos el mismo truco para prestar un poco más, dándonos 10 - 1 = 1, que ponemos en el tercer lugar del resultado.
- En cuarto lugar, nuevamente tenemos un poco prestado para tratar. Reste el bit prestado del 1 que ya está allí: 1 - 1 = 0. Podríamos escribir esto en frente del resultado, pero ya que es el final de la resta no hay necesidad.
Hay un número menor que cero?
¿Recuerdas cómo aprendiste sobre los números negativos? Parte de la idea es que puedes restar cualquier número de cualquier otro número y aún obtener un número. Entonces 7 - 5 es 2; 6 - 5 es 1; 5 - 5 es 0; ¿Qué es 4 - 5? Bueno, una forma de razonar sobre tales números es simplemente aplicar el mismo método que el anterior para hacer la resta.
Como ejemplo, intentemos 2 - 7 en binario:
10 -
111
_______
...1011
Empecé de la misma manera que antes:
- En el lugar más a la derecha, reste 1 de 0, que requiere un bit prestado. 10 - 1 = 1, por lo que el último bit del resultado es 1.
- En el segundo lugar más a la derecha, tenemos 1 - 1 con un bit de préstamo adicional, por lo que tenemos que restar otro 1. Esto significa que tenemos que pedir prestado nuestro propio bit, dando 11 - 1 - 1 = 1. Escribimos 1 en el segundo lugar más a la derecha.
- En tercer lugar, ¡no hay más bits en el número superior! Pero sabemos que podemos pretender que hay un 0 en frente, al igual que lo haríamos si el número inferior se quedó sin bits. Entonces tenemos 0 - 1 - 1 debido al bit de préstamo del segundo lugar. ¡Tenemos que pedir prestado un poco otra vez! De todos modos tenemos 10 - 1 - 1 = 0, que escribimos en el tercer lugar desde la derecha.
Ahora ha sucedido algo muy interesante: los dos operandos de la sustracción no tienen más dígitos, ¡pero aún tenemos un poco de préstamo del que ocuparnos! Oh, bueno, continuemos como lo hemos estado haciendo. Tenemos 0 - 0, ya que ni el operando superior ni el inferior tienen bits aquí, pero debido al bit de préstamo en realidad es 0 - 1.
(¡Tenemos que pedir prestado otra vez! Si seguimos pidiendo prestado de esta manera, tendremos que declararnos en bancarrota pronto).
De todos modos, pedimos prestado el bit, y obtenemos 10 - 1 = 1, que escribimos en el cuarto lugar desde la derecha.
Ahora, cualquier persona con la mitad de la mente está a punto de ver que vamos a seguir pidiendo prestado hasta que las vacas vuelvan a casa, ¡porque no hay más cosas para todos! Nos escapamos de ellos dos lugares atrás si lo olvidaste. Pero si tratas de seguir así se vería así:
...00000010
...00000111
___________
...11111011
- En el quinto lugar obtenemos 0 - 0 - 1, y tomamos prestado un poco para obtener 10 - 0 - 1 = 1.
- En el sexto lugar obtenemos 0 - 0 - 1, y tomamos prestado un poco para obtener 10 - 0 - 1 = 1.
- En el séptimo lugar obtenemos 0 - 0 - 1, y tomamos prestado un poco para obtener 10 - 0 - 1 = 1.
... Y así continúa para tantos lugares como quieras. Por cierto, acabamos de derivar la forma binaria del complemento de dos de -5 .
Podrías probar esto con cualquier par de números que te gusten, y generar la forma complementaria de los dos de cualquier número negativo. Si intenta hacer 0 - 1, verá por qué -1 se representa como ...11111111 . También sabrá por qué los dos números negativos del complemento tienen un 1 como su bit más significativo (el "bit principal" en la pregunta original).
En la práctica, su computadora no tiene infinitos bits para almacenar números negativos, por lo que generalmente se detiene después de un número más razonable, como 32. ¿Qué hacemos con el bit de préstamo adicional en la posición 33? Eh, solo lo ignoramos en silencio y esperamos que nadie se dé cuenta. Cuando algunos notan que nuestro nuevo sistema numérico no funciona, lo llamamos desbordamiento de enteros .
Notas finales
Esta no es la única manera de hacer que nuestro sistema numérico funcione, por supuesto. Después de todo, si le debo $ 5, no diría que su saldo actual fue de $ ... 999999995.
Pero hay algunas cosas interesantes acerca del sistema que acabamos de derivar, como el hecho de que la resta le da el resultado correcto en este sistema, incluso si ignora el hecho de que uno de los números es negativo. Normalmente, tenemos que pensar en sustracciones con pasos condicionales: para calcular 2 - 7, primero tenemos que descubrir que 2 es menor que 7, por lo que calculamos 7 - 2 = 5, y luego colocamos un signo menos al frente para obtener 2 - 7 = -5. Pero con el complemento de dos, simplemente hacemos la resta y no nos importa qué número es más grande, y el resultado correcto sale solo. Y otros han mencionado que la adición funciona muy bien, al igual que la multiplicación.
No usas el bit adelantado, por ejemplo. Por ejemplo, en un char firmado con 8 bits,
11111111
representa -1. Puede probar el bit inicial para determinar si es un número negativo.
Hay una serie de razones para usar el complemento de 2, pero el primero y el mejor es la conveniencia. Tome el número anterior y agregue 2. ¿Con qué terminamos?
00000001
Puede agregar y restar números de complemento de 2 básicamente gratis. Esto fue un gran problema históricamente, porque la lógica es muy simple; no necesita hardware dedicado para manejar los números con signo. Utiliza menos transistores, necesita un diseño menos complicado, etc. Se remonta a los microprocesadores de 8 bits, que ni siquiera tenían instrucciones multiplas incorporadas (incluso muchos de 16 bits no los tenían, como el 65c816 utilizado en apple IIe y Super NES).
Dicho esto, la multiplicación es relativamente trivial con el complemento de 2 también, así que no es gran cosa.
Los complementos (incluidos elementos como el complemento 9s en decimal, calculadoras mecánicas / máquinas sumadoras / cajas registradoras) han existido por siempre. En el complemento de nueves con cuatro dígitos decimales, por ejemplo, los valores en el rango 0000..4999 son positivos, mientras que los valores en 5000..9999 son negativos. Ver http://en.wikipedia.org/wiki/Method_of_complements para más detalles.
Esto da lugar directamente al complemento 1 en binario, y en el complemento 1s y 2s, el bit más alto actúa como un "bit de signo". Esto no explica exactamente cómo las computadoras pasaron del complemento de uno al complemento de dos (utilizo la convención de apóstrofes de Knuth cuando deletreo estas como palabras con apóstrofes, por cierto). Creo que fue una combinación de suerte, irritación en el "cero negativo", y la forma en que el complemento requiere un acarreo final (versus el complemento a dos, que no lo requiere).
En un sentido lógico, no importa qué bit utilice para representar signos, pero para fines prácticos, usar el bit superior y el complemento a dos simplifica el hardware. Cuando los transistores eran caros, esto era bastante importante. (O incluso tubos, aunque creo que la mayoría, si no todas las computadoras con tubos de vacío, se usaron como complemento. En cualquier caso, fueron más antiguas que el lenguaje C).
En resumen, la historia se remonta mucho antes que las computadoras electrónicas y el lenguaje C, y no había ninguna razón para cambiar desde una buena forma de implementar esto mecánicamente, al convertir de calculadoras mecánicas a ENIAC de tubo de vacío a computadoras transistorizadas y luego a " chips ", MSI, LSI, VLSI, y en adelante.