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

12

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

mi pregunta en parte es por qué deben estar en el conjunto de instrucciones como ¿Se opone a ser soportado por un compilador?

    
pregunta jtw 14.10.2016 - 22:09

9 respuestas

41

Los números sin firmar 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 de operación son simplemente bits. El direccionamiento de memoria / pila y la aritmética son los cimientos del microprocesador, bueno, el procesamiento. Avanzando en la pirámide de abstracción, otra interpretación frecuente de bits es como un personaje (ASCII, Unicode, EBCDIC). Luego hay otras interpretaciones, como el punto flotante IEEE, RGBA para gráficos, etc. Ninguno de estos son números con signo simple (IEEE FP no es simple, y el uso aritmético es muy complicado).

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

    
respondido por el Kristian H 14.10.2016 - 23:19
19

La mayor parte del costo de 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 33er bit de orden superior en una computadora de 32 bits)

Con la combinación adecuada de prueba de estos tres bits después de la operación de resta, podemos determinar todas las operaciones relacionales firmadas, así como todas las operaciones relacionales no firmadas (estos bits también son la forma en que se detecta el desbordamiento, firmado versus no firmado). El mismo hardware básico de ALU se puede compartir 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 una gran cantidad de 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 ligeramente la densidad de la instrucción. Sin embargo, es bastante normal que el hardware tenga muchas instrucciones que no se usan en ningún idioma.

    
respondido por el Erik Eidt 15.10.2016 - 00:38
13

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

Considere el INT PK incrementado 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 MITAD de tantos registros como podría para el mismo tamaño de campo sin NINGUNA ventaja.

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

Desde la perspectiva del hardware, los enteros sin signo son simples. Probablemente sean la estructura de bits más fácil para realizar operaciones matemáticas. Y, sin duda, podríamos simplificar el hardware mediante la simulación de tipos de enteros (¡o incluso de punto flotante!) En un compilador. Entonces, ¿por qué los enteros con signo y sin signo están implementados en hardware?

Bueno ... rendimiento!

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

    
respondido por el svidgen 14.10.2016 - 23:01
9

Su pregunta consta de dos partes:

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

  2. ¿Valen la pena los enteros sin signo?

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 cuales los valores negativos no tienen significado. Claro, podrías decir que la respuesta a la pregunta "¿Cuántas manzanas tengo?" podría ser un número negativo si le debes algunas manzanas a alguien, pero ¿qué pasa con la pregunta de "cuánta memoria tengo?" --No puedes 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. Usted ve, 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 no firmados; tiene un solo multiplicador, que funciona de una manera ligeramente diferente dependiendo de la naturaleza de la operación. Para admitir la multiplicación firmada se requiere un poco más de circuitos que sin firmar, pero como es necesario que se admita de todos modos, la multiplicación sin firma es prácticamente gratuita, se incluye en el paquete.

En cuanto a la suma y la resta, no hay ninguna diferencia en los circuitos. Si lee la llamada representación de dos enteros del complemento , encontrará que está diseñado de manera tan inteligente que estas operaciones se pueden realizar 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 derivación condicional (salto), que funcionan al observar diferentes indicadores de la CPU que son establecido por la instrucción precedente (comparación). En esta respuesta: enlace 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 firmada o no firmada depende de los indicadores que examina.

    
respondido por el Mike Nakis 14.10.2016 - 23:25
7

Los microprocesadores están intrínsecamente sin firmar. Los números firmados son lo que se implementa, no al revés.

Las computadoras pueden y funcionan bien sin números firmados, pero nosotros, los humanos que necesitamos números negativos, se inventó la firma.

    
respondido por el Pieter B 14.10.2016 - 23:11
3

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

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

Mi ejemplo favorito proviene de bitboards en los motores de ajedrez. Hay 64 casillas en un tablero de ajedrez, por lo tanto, unsigned long proporciona 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 cambio!), Es fácil ver por qué es más fácil no tener que preocuparse por las cosas especiales que suceden si se establece el MSB. Se puede hacer con una firma larga, pero es un lote más fácil de usar sin firmar.

    
respondido por el riwalk 14.10.2016 - 23:00
3

Con un fondo de matemáticas puras, esta es una versión ligeramente más matemática para cualquier persona interesada.

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

Donde las cosas difieren es en dos lugares: uno es operaciones de comparación. En cierto sentido, los enteros modulo 256 se consideran mejor como un círculo de números (como los enteros modulo 12 en una esfera analógica antigua). Para hacer significativas las comparaciones numéricas (es x < y), necesitamos decidir qué números son menos que otros. Desde el punto de vista del matemático, queremos incrustar los enteros modulo 256 en el conjunto de todos los enteros de alguna manera. Asignar el entero de 8 bits cuya representación binaria es todos ceros al entero 0 es lo más 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, asignando '0-1' al entero -1, y '0-1-1' al entero -2. Debemos asegurarnos de que esta integració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. Hay esencialmente 255 formas de hacerlo con un entero de 8 bits (según a que mínimo desea, de 0 a -255). Entonces puedes 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 es mayor que 0, y uno con una división de aproximadamente 50/50 alrededor de 0. Todas las demás posibilidades se pueden emular fácilmente al traducir números a través de un extra 'agregue y sub' antes de las operaciones, y la necesidad de esto es tan rara que no puedo pensar en un ejemplo explícito en software moderno (ya que puede trabajar con una mantisa más grande, digamos 16 bits).

El otro problema es el de la asignación de un entero de 8 bits en el espacio de enteros de 16 bits. ¿-1 va a -1? Esto es lo que quieres si 0xFF pretende representar -1. En este caso, la extensión de la señal es lo más sensato, de modo que 0xFF pase a 0xFFFF. Por otro lado, si se suponía que 0xFF representaba 255, entonces desea que se asigne a 255, por lo tanto, a 0x00FF, en lugar de a 0xFFFF.

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

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

    
respondido por el John Allsup 16.10.2016 - 10:14
2

Permite examinar 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 varias marcas; las analizaremos a continuación)
  • CMP (que es esencialmente 'SUB y descarta el resultado, solo conserva las banderas')
  • LSH (desplazamiento a la izquierda, establecer un indicador en desbordamiento)
  • RSH (desplazamiento a la derecha, establece un indicador 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 de manera conveniente para operar en tipos más grandes que los registros de la CPU
  • MUL (multiplica, establece banderas, etc., no está disponible universalmente)
  • DIV (división, configuración de indicadores, etc., muchas arquitecturas de CPU carecen de esto)
  • Mover desde un tipo entero más pequeño (por ejemplo, de 16 bits) a uno más grande (por ejemplo, de 32 bits). Para enteros con signo, esto generalmente se llama MOVSX (mover con extensión de signo).

También necesita instrucciones lógicas:

  • rama en cero
  • Rama en mayor
  • Rama en menos
  • Rama en el desbordamiento
  • Versiones negadas de todo lo anterior

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

  • cero. Se establece si la resta dio como resultado un valor de cero.
  • Desbordamiento. Establezca si la resta tomó prestado un valor del bit más significativo.
  • firmar. Establecer en el bit de signo del resultado.

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

  • Sucursal en cero: si se establece el indicador cero
  • Ramifique con menos: si el indicador de signo es diferente al indicador de desbordamiento
  • Rama en mayor: si el indicador de signo es igual al indicador de desbordamiento, y el indicador de cero está claro.

Las negaciones de estos deben seguirse obviamente de cómo se implementan.

Por lo tanto, su diseño existente ya implementa todos estos elementos 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 cambio a la derecha para los valores firmados retiene el valor del bit más significativo. Para los valores sin firmar, 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 tiene tiene un manejo especial, pero solo porque se ha generado en un par de registros, pero tenga en cuenta que esto La instalación en realidad se usa muy raramente, por lo que sería un candidato más obvio a dejar fuera de un procesador que los tipos sin firma)
  • DIV: no se requieren cambios
  • Mover de un tipo más pequeño a otro más grande: es necesario agregar MOVZX, mover con extensión cero. Tenga en cuenta que MOVZX es extremadamente fácil de implementar.
  • Ramificación en cero - sin cambios
  • Ramifique con menos - salta cuando lleve el conjunto de banderas.
  • Rama en mayor - salta si la bandera de acarreo y el cero se borran ambas.

Tenga en cuenta que, en cada caso, las modificaciones son muy simples y se pueden implementar simplemente activando o desactivando una pequeña sección de circuitos, o agregando un nuevo registro de bandera que se pueda controlar 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é se debe hacer , tenga en cuenta que las direcciones de memoria (y las compensaciones en los arreglos) son valores intrínsecamente 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.

    
respondido por el Periata Breatta 15.10.2016 - 11:30
2

Los números sin firmar existen en gran medida para manejar situaciones en las que se necesita un anillo algebraico de ajuste (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 ejemplo del mundo real, si un medidor de utilidad 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 C se implementó por primera vez, había No se pueden usar tipos enteros sin signo, pero los tipos con signo se podrían usar para modular aritmética que envolvió entre 32767 y -32768 en lugar de entre 65535 y 0. Las instrucciones de enteros en algunas otras plataformas no envolver las cosas limpiamente, sin embargo; en lugar de requerir que las implementaciones debe emular los enteros de complemento a dos utilizados en el PDP-11, el lenguaje en su lugar, se agregaron tipos sin firmar que en su mayoría tenían que comportarse como algebraicos suena, y permite que los tipos 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). Eso por lo tanto, se volvió común usar tipos sin firma para contener tales cantidades (por ejemplo, tamaño_t). Desafortunadamente, no hay nada en el idioma para distinguir entre tipos que deberían comportarse como números con un bit extra de Rango positivo, frente a 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 funciona como:

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

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

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

    
respondido por el supercat 15.10.2016 - 21:39

Lea otras preguntas en las etiquetas