¿Por qué se implementan números sin signo?

No puedo entender por qué los sistemas de microprocesador implementan números sin signo. Supongo que el costo es solo el doble del número de ramificaciones condicionales, ya que mayor que, menor que, .etc, necesita un algoritmo diferente al de signo, ¿todavía hay algoritmos para los que los números sin signo son una ventaja significativa?

mi pregunta es, en parte, ¿por qué necesitan estar en el conjunto de instrucciones en lugar de ser compatibles con un compilador?

Los números sin signo son una interpretación de una secuencia de bits. También es la interpretación más simple y más utilizada internamente para la CPU porque las direcciones y los códigos operativos son simplemente bits. El direccionamiento de memoria / pila y la aritmética son las bases del microprocesador, bueno, el procesamiento. Subiendo por la pirámide de abstracción, otra interpretación frecuente de bits es como un carácter (ASCII, Unicode, EBCDIC). Luego hay otras interpretaciones como IEEE Floating point, RGBA para gráficos, etc. Ninguno de estos son números con signo simple (IEEE FP no es simple, y la aritmética que los usa es muy complicada).

Además, con la aritmética sin signo, es bastante sencillo (si no de la manera más eficiente) implementar los otros. Lo contrario no es cierto.

La mayor parte del costo del hardware para las operaciones de comparación es la resta. La salida de la resta utilizada por comparación es esencialmente tres bits de estado:

• si todos los bits son cero (es decir, la misma condición),
• el bit de signo del resultado
• el bit de acarreo de la resta (es decir, el bit 33 de orden superior en una computadora de 32 bits)

Con la combinación adecuada de probar estos tres bits después de la operación de sustracción, podemos determinar todas las operaciones relacionales con signo, así como todas las operaciones relacionales sin signo (estos bits también son cómo se detecta el desbordamiento, con signo y sin signo). Se puede compartir el mismo hardware ALU básico para implementar todas estas comparaciones (sin mencionar la instrucción de resta), hasta la verificación final de esos tres bits de estado, que difiere según la comparación relacional deseada. Por lo tanto, no es mucho hardware adicional.

El único costo real es la necesidad de codificar modos de comparación adicionales en la arquitectura del conjunto de instrucciones, lo que puede disminuir marginalmente la densidad de la instrucción. Aún así, es bastante normal que el hardware tenga muchas instrucciones que no son utilizadas por ningún idioma.

Porque, si necesita contar algo que siempre es >= 0, reduciría innecesariamente su espacio de conteo a la mitad usando enteros con signo.

Considere la PK PK INT incrementada automáticamente que podría estar poniendo en las tablas de su base de datos. Si usa un entero con signo allí, su tabla almacena la MISMA cantidad de registros que pueda para el mismo tamaño de campo SIN beneficio.

O los octetos de un color RGBa. No queremos comenzar a contar torpemente este concepto de número positivo natural en un número negativo. Un número firmado podría romper el modelo mental o reducir a la mitad nuestro espacio. Un entero sin signo no solo coincide con el concepto, sino que proporciona el doble de resolución.

Desde la perspectiva del hardware, los enteros sin signo son simples. Son probablemente la estructura de bits más fácil para realizar las matemáticas. Y, sin duda, podríamos simplificar el hardware simulando tipos enteros (¡o incluso coma flotante!) En un compilador. Entonces, ¿por qué se implementan enteros sin signo y con signo en el hardware?

Bueno ... rendimiento!

Es más eficiente implementar enteros firmados en hardware que en software. El hardware puede recibir instrucciones para realizar operaciones matemáticas en cualquier tipo de entero en una sola instrucción. Y eso es muy bueno , porque el hardware rompe bits más o menos en paralelo. Si intenta simular eso en el software, el tipo entero que elija "simular" requerirá indudablemente muchas instrucciones y será notablemente más lento.

Su pregunta consta de dos partes:

1. ¿Cuál es el propósito de los enteros sin signo?

2. ¿Los enteros sin signo valen la pena?

1. ¿Cuál es el propósito de los enteros sin signo?

Los números sin signo, simplemente, representan una clase de cantidades para las que los valores negativos no tienen sentido. Claro, se podría decir que la respuesta a la pregunta "¿cuántas manzanas tengo?" podría ser un número negativo si le debe algunas manzanas a alguien, pero ¿qué pasa con la pregunta de "cuánta memoria tengo?" - no puede tener una cantidad negativa de memoria. Por lo tanto, los enteros sin signo son muy adecuados para representar tales cantidades, y tienen la ventaja de poder representar el doble del rango de valores positivos que los enteros con signo. Por ejemplo, el valor máximo que puede representar con un entero con signo de 16 bits es 32767, mientras que con un entero sin signo de 16 bits es 65535.

2. ¿Los enteros sin signo valen la pena?

Los enteros sin signo realmente no representan ningún problema, así que sí, valen la pena. Verá, no requieren un conjunto adicional de "algoritmos"; los circuitos necesarios para implementarlos son un subconjunto de los circuitos necesarios para implementar enteros con signo.

Una CPU no tiene un multiplicador para enteros con signo y un multiplicador diferente para los sin signo; tiene solo un multiplicador, que funciona de una manera ligeramente diferente dependiendo de la naturaleza de la operación. El soporte de la multiplicación con signo requiere un poco más de circuito que sin signo, pero dado que de todos modos debe ser compatible, la multiplicación sin signo es prácticamente gratuita, está incluida en el paquete.

En cuanto a la suma y la resta, no hay diferencia en el circuito en absoluto. Si lee la llamada representación de los enteros del complemento de dos, encontrará que está tan inteligentemente diseñado que estas operaciones pueden realizarse exactamente de la misma manera, independientemente de la naturaleza de los enteros.

La comparación también funciona de la misma manera, ya que no es más que restar-y-descartar-el-resultado, la única diferencia está en las instrucciones de ramificación condicional (salto), que funcionan mirando diferentes indicadores de la CPU que son establecidos por el instrucción anterior (de comparación). En esta respuesta: /programming//a/9617990/773113 puede encontrar una explicación de cómo funcionan en la arquitectura Intel x86. Lo que sucede es que la designación de una instrucción de salto condicional como con signo o sin signo depende de qué indicadores examina.

Los microprocesadores son inherentemente sin signo. Los números con signo son lo que se implementa, no al revés.

Las computadoras pueden y funcionan bien sin números con signo, pero somos nosotros, los humanos que necesitamos números negativos, por lo tanto, se inventó la firma.

Debido a que tienen un bit más que está fácilmente disponible para el almacenamiento, y no tiene que preocuparse por los números negativos. No hay mucho más que eso.

Ahora, si necesita un ejemplo de dónde necesitaría este bit extra, hay mucho que encontrar si lo mira.

Mi ejemplo favorito proviene de los bitboards en los motores de ajedrez. Hay 64 casillas en un tablero de ajedrez, por lo que unsigned longproporciona un almacenamiento perfecto para una variedad de algoritmos que giran en torno a la generación de movimientos. Teniendo en cuenta el hecho de que necesita operaciones binarias (¡así como operaciones de desplazamiento!), Es fácil ver por qué es más fácil no tener que preocuparse por las cosas especiales que suceden si se configura el MSB. Se puede hacer con signo largo, pero es mucho más fácil de usar sin signo.

Con un fondo matemático puro, esta es una toma un poco más matemática para cualquier persona interesada.

Si comenzamos con un entero de 8 bits con signo y sin signo, lo que tenemos es básicamente el módulo 256 de enteros, en lo que respecta a la suma y la multiplicación, siempre que el complemento de 2 se use para representar enteros negativos (y así es como lo hace todo procesador moderno) .

Donde las cosas difieren es en dos lugares: uno es las operaciones de comparación. En cierto sentido, los números enteros módulo 256 se consideran mejor un círculo de números (como lo hacen los números enteros módulo 12 en una esfera de reloj analógica anticuada). Para que las comparaciones numéricas (es x <y) sean significativas, necesitamos decidir qué números son menores que otros. Desde el punto de vista del matemático, queremos integrar los enteros módulo 256 en el conjunto de todos los enteros de alguna manera. Mapear el entero de 8 bits cuya representación binaria es todos ceros al entero 0 es lo obvio. Luego podemos proceder a mapear otros para que '0 + 1' (el resultado de poner a cero un registro, digamos ax, y su incremento en uno, a través de 'inc ax') vaya al número entero 1, y así sucesivamente. Podemos hacer lo mismo con -1, por ejemplo, mapeando '0-1' al entero -1 y '0-1-1' al entero -2. Debemos asegurarnos de que esta incrustación sea una función, por lo que no se puede asignar un solo entero de 8 bits a dos enteros. Como tal, esto significa que si asignamos todos los números al conjunto de enteros, 0 estará allí, junto con algunos enteros menores que 0 y algunos más que 0. Existen esencialmente 255 formas de hacer esto con un entero de 8 bits (de acuerdo con a qué mínimo desea, de 0 a -255). Luego puede definir 'x <y' en términos de '0 <y - x'.

Hay dos casos de uso comunes, para los cuales el soporte de hardware es sensato: uno con todos los enteros distintos de cero que son mayores que 0, y otro con un 50/50 aproximadamente dividido alrededor de 0. Todas las demás posibilidades se emulan fácilmente traduciendo números mediante un 'add adicional y sub 'antes de las operaciones, y la necesidad de esto es tan rara que no puedo pensar en un ejemplo explícito en el software moderno (ya que puede trabajar con una mantisa más grande, digamos 16 bits).

El otro problema es el de mapear un entero de 8 bits en el espacio de enteros de 16 bits. ¿-1 va a -1? Esto es lo que quiere si 0xFF está destinado a representar -1. En este caso, la extensión de señal es lo más sensato, para que 0xFF vaya a 0xFFFF. Por otro lado, si 0xFF estaba destinado a representar 255, entonces desea asignarlo a 255, por lo tanto, a 0x00FF, en lugar de 0xFFFF.

Esta es la diferencia entre las operaciones de 'desplazamiento' y 'desplazamiento aritmético' también.

Sin embargo, en última instancia, se reduce al hecho de que los int en el software no son enteros, sino representaciones en binario, y solo algunos pueden representarse. Cuando se diseña hardware, se deben elegir qué hacer de forma nativa en hardware. Dado que con el complemento de 2 las operaciones de suma y multiplicación son idénticas, tiene sentido representar enteros negativos de esta manera. Entonces es solo una cuestión de operaciones que dependen de los enteros que sus representaciones binarias deben representar.

Examinemos el costo de implementación para agregar enteros sin signo a un diseño de CPU con enteros con signo existentes.

Una CPU típica necesita las siguientes instrucciones aritméticas:

• AGREGAR (que agrega dos valores y establece un indicador si la operación se desborda)
• SUB (que resta un valor de otro y establece varios indicadores; discutiremos estos a continuación)
• CMP (que es esencialmente 'SUB y descartar el resultado, solo mantener las banderas')
• LSH (desplazamiento a la izquierda, establecer una bandera en desbordamiento)
• RSH (desplazamiento a la derecha, establezca una bandera si se desplaza un 1)
• Variantes de todas las instrucciones anteriores que manejan el transporte / préstamo de las banderas, lo que le permite encadenar las instrucciones convenientemente para operar en tipos más grandes que los registros de la CPU
• MUL (multiplicar, establecer banderas, etc., no disponible universalmente)
• DIV (dividir, establecer marcas, etc., muchas arquitecturas de CPU carecen de esto)
• Pase de un tipo entero más pequeño (por ejemplo, 16 bits) a uno más grande (por ejemplo, 32 bits). Para enteros con signo, esto generalmente se llama MOVSX (mover con signo extendido).

También necesita instrucciones lógicas:

• Rama en cero
• Rama en mayor
• Se ramifica en menos
• Rama en desbordamiento
• Versiones negadas de todo lo anterior

Para realizar las ramas anteriores en comparaciones de enteros con signo, la forma más fácil es hacer que la instrucción SUB establezca los siguientes indicadores:

• Cero. Establezca si la resta resultó en un valor de cero.
• Desbordamiento. Establezca si la resta tomó prestado un valor del bit más significativo.
• Firmar. Establezca el bit de signo del resultado.

Luego, las ramas aritméticas se implementan de la siguiente manera:

• Ramificación en cero: si se establece el indicador de cero
• Se ramifica en menos: si el indicador de signo es diferente al indicador de desbordamiento
• Ramificación en mayor: si el indicador de signo es igual al indicador de desbordamiento, y el indicador de cero está claro.

Las negaciones de estos deberían seguir obviamente de cómo se implementan.

Por lo tanto, su diseño existente ya implementa todo esto para enteros con signo. Ahora consideremos lo que debemos hacer para agregar enteros sin signo:

• ADD: la implementación de ADD es idéntica.
• SUB: necesitamos agregar un indicador adicional: el indicador de acarreo se establece cuando se toma prestado un valor más allá del bit más significativo del registro.
• CMP: no cambia
• LSH - no cambia
• RSH: el desplazamiento a la derecha para valores con signo retiene el valor del bit más significativo. Para valores sin signo, deberíamos establecerlo en cero.
• MUL - si su tamaño de salida es el mismo que el de entrada, no se requiere un manejo especial (x86 hace tener un manejo especial, pero sólo porque no tiene salida en un par de registros, pero tenga en cuenta que esta instalación es en realidad muy rara vez se utiliza, por lo que sería un candidato más obvio para dejar fuera de un procesador que los tipos sin firmar)
• DIV - no se requieren cambios
• Muévase del tipo más pequeño al más grande: necesita agregar MOVZX, muévase con extensión cero. Tenga en cuenta que MOVZX es extremadamente simple de implementar.
• Ramificación en cero - sin cambios
• Salta con menos saltos cuando llevas el set de banderas.
• Ramificarse en mayor - salta si lleva bandera y cero ambos despejados.

Tenga en cuenta que en cada caso, las modificaciones son muy simples y pueden implementarse simplemente activando o desactivando una pequeña sección de circuitos, o agregando un nuevo registro de indicador que puede controlarse mediante un valor que debe calcularse como parte de la implementación de la instrucción de todos modos.

Por lo tanto, el costo de agregar instrucciones sin firmar es muy pequeño . En cuanto a por qué debería hacerse , tenga en cuenta que las direcciones de memoria (y las compensaciones en matrices) son valores inherentemente sin signo. Como los programas pasan mucho tiempo manipulando direcciones de memoria, tener un tipo que las maneje correctamente hace que los programas sean más fáciles de escribir.

Los números sin signo existen en gran medida para manejar situaciones en las que uno necesita un anillo algebraico envolvente (para un tipo sin signo de 16 bits, sería el anillo de números enteros congruente mod 65536). Tome un valor, agregue cualquier cantidad menor que el módulo, y la diferencia entre los dos valores será la cantidad que se agregó. Como un ejemplo del mundo real, si un medidor de servicio público lee 9995 al comienzo de un mes y uno usa 23 unidades, el medidor leerá 0018 al final del mes. Cuando se usa un tipo de anillo algebraico, no hay necesidad de hacer nada especial para lidiar con el desbordamiento. Restar 9995 de 0018 producirá 0023, precisamente el número de unidades que se usaron.

En el PDP-11, la máquina para la cual se implementó C por primera vez, no había tipos enteros sin signo, pero los tipos con signo podían usarse para la aritmética modular que se ajustaba entre 32767 y -32768 en lugar de entre 65535 y 0. Las instrucciones enteras en algún otro Sin embargo, las plataformas no envolvieron las cosas de manera limpia; en lugar de requerir que las implementaciones deben emular los enteros del complemento a dos utilizados en el PDP-11, el lenguaje agregó tipos sin signo que en su mayoría tenían que comportarse como anillos algebraicos, y permitió que los tipos de enteros con signo se comporten de otras maneras en caso de desbordamiento.

En los primeros días de C, había muchas cantidades que podían exceder 32767 (el INT_MAX común) pero no 65535 (el UINT_MAX común). Por lo tanto, se hizo común usar tipos sin signo para contener tales cantidades (por ejemplo, size_t). Desafortunadamente, no hay nada en el lenguaje para distinguir entre los tipos que deberían comportarse como números con un rango positivo adicional, frente a los tipos que deberían comportarse como anillos algebraicos. En cambio, el lenguaje hace que los tipos más pequeños que "int" se comporten como números, mientras que los tipos de tamaño completo se comportan como anillos algebraicos. En consecuencia, llamando a la función como:

uint32_t mul(uint16_t a, uint16_t b) { return a*b; }

with (65535, 65535) tendrá un comportamiento definido en sistemas con int16 bits (es decir, retorno 1), un comportamiento diferente con int33 bits o más (retorno 0xFFFE0001) y Comportamiento indefinido en sistemas donde "int" está en cualquier lugar entre [tenga en cuenta que gcc generalmente producirá resultados correctos aritméticamente con resultados entre INT_MAX + 1u y UINT_MAX, ¡pero a veces generará código para la función anterior que falla con tales valores!]. No muy útil

Aún así, la falta de tipos que se comportan consistentemente como números o consistentemente como un anillo algebraico no cambia el hecho de que los tipos de anillo algebraico son casi indispensables para algunos tipos de programación.