Por que os números não assinados são implementados?

12

Não consigo entender por que os sistemas de microprocessadores implementam números não assinados. Eu acho que o custo é apenas o dobro do número de ramificações condicionais, já que maior que, menor que .etc, precisa de um algoritmo diferente do assinado.

minha pergunta em parte é por que eles precisam estar no conjunto de instruções em vez de serem suportados por um compilador?

jtw
fonte
27
Basicamente, os números não assinados são o padrão, assinados são implementados para fornecer números negativos.
Pieter B
37
Muitos dados do mundo são não numéricos. Dados não numéricos são facilmente manipulados usando tipos não assinados. O fato de o Java não ter tipos numéricos não assinados é uma falha, o que causa muitos bugs em coisas que precisam manipular dados não numéricos (por exemplo, compactação, etc.).
precisa
6
@jtw Erik diz que não existe uma cor de pixel negativa ou um caracter negativo. Portanto, seria um desperdício usar números inteiros assinados para isso, você abriria metade do espaço de endereço.
Martin Maat
26
Não tenho certeza se estou sozinho aqui, mas acho surpreendentemente raro precisar de números inteiros assinados ao desenvolver aplicativos. Na maioria das vezes, o que eu preciso é de um número natural (não assinado) (um tamanho positivo, geralmente) ou um número de ponto flutuante assinado. Exceções são coisas como moeda, mas são muito raras; para mim, números inteiros não assinados são a norma e números inteiros assinados são a exceção!
Thomas
11
Da perspectiva de uma CPU, praticamente todos os números não são assinados. Algumas instruções podem interpretar os bits como assinados (.eg aritmético-deslocamento para a direita), mas, na verdade, o complemento de dois permite que a CPU trate números inteiros assinados como números inteiros não assinados, o que significa que nenhum (ou muito pouco) circuito especial é necessário para que a CPU suporte ambos .
quer

Respostas:

39

Números não assinados são uma interpretação de uma sequência de bits. É também a interpretação mais simples e mais usada internamente na CPU, porque endereços e códigos op são simplesmente bits. O endereçamento de memória / pilha e a aritmética são os alicerces do microprocessador, bem, do processamento. Subindo na pirâmide de abstração, outra interpretação frequente de bits é como um caractere (ASCII, Unicode, EBCDIC). Existem outras interpretações, como ponto flutuante IEEE, RGBA para gráficos e assim por diante. Nenhum desses números é simples (o IEEE FP não é simples e a aritmética é muito complicada).

Além disso, com aritmética sem sinal, é bastante simples (se não com mais eficiência) implementar os outros. O inverso não é verdadeiro.

Kristian H
fonte
3
EBCDIC possui apenas um "I".
Ruslan #
4
@Ruslan - mas é pronunciado como se tivesse dois. <g>
Pete Becker
5
@PeteBecker não, não é. EBCDIC é pronunciado eb -see-dick.
quer
19

A maior parte do custo de hardware para operações de comparação é a subtração. A saída da subtração usada por comparação é essencialmente três bits de estado:

  • se todos os bits são zero (ou seja, a mesma condição),
  • o pouco sinal do resultado
  • o bit de transporte da subtração (ou seja, o 33º bit de ordem superior em um computador de 32 bits)

Com a combinação adequada de testar esses três bits após a operação de subtração, podemos determinar todas as operações relacionais assinadas, bem como todas as operações relacionais não assinadas (esses bits também são como o estouro é detectado, assinado versus não assinado). O mesmo hardware ALU básico pode ser compartilhado para implementar todas essas comparações (sem mencionar a instrução de subtração), até a verificação final desses três bits de estado, que difere conforme a comparação relacional desejada. Portanto, não é muito hardware extra.

O único custo real é a necessidade da codificação de modos adicionais de comparação na arquitetura do conjunto de instruções, o que pode diminuir marginalmente a densidade da instrução. Ainda assim, é bastante normal que o hardware tenha muitas instruções que não são usadas por nenhum idioma.

Erik Eidt
fonte
1
A comparação de números não assinados não requer subtração. isso pode ser alcançado por comparação bit a bit da esquerda para a direita.
Jonathan Rosenne
10
@ JonathanRosenne Mas não é assim que os processadores o implementam. Pelo contrário, é quase impensável para um processador de complemento de 2 não implementar subtração (com ou sem carry / emprestar) em sua ULA. O pensamento posterior imediato de um designer é usar essa ALU necessária para matar outro pássaro com a mesma pedra, para comparação. A comparação simplesmente se torna uma subtração em que o resultado não é gravado de volta no arquivo de registro.
Iwillnotexist Idonotexist
4
+1: esta é a resposta correta para a pergunta. Resumindo: porque a implementação de operações não assinadas é quase gratuita quando você já implementou o assinado .
Periata Respira
10
@PeriataBreatta Também funciona ao contrário. Os números assinados e não assinados nas CPUs modernas são quase idênticos, que é o ponto principal que o OP não reconheceu. Mesmo as instruções de comparação são os mesmos para assinado e sem assinatura - que é uma das razões pelas quais complemento de dois ganhou o inteiro assinado guerras :)
Luaan
3
@svidgen> como outras respostas, ele funciona ao contrário. A preocupação principal são os números não assinados, que são usados ​​basicamente para tudo (endereço de memória, io / portas, representações de caracteres, ...). Os números assinados ficam baratos depois de você ter assinado, e são úteis no raro evento em que são desejáveis.
espectros
14

Porque, se você precisar contar algo que sempre é >= 0, reduziria desnecessariamente o seu espaço de contagem pela metade usando números inteiros assinados.

Considere o INT PK com incremento automático que você pode estar colocando nas tabelas do banco de dados. Se você usar um número inteiro assinado lá, sua tabela armazenará MEIO tantos registros quanto possível para o mesmo tamanho de campo, sem nenhum benefício.

Ou os octetos de uma cor RGBa. Não queremos começar desajeitadamente a contar esse conceito de número naturalmente positivo em um número negativo. Um número assinado quebraria o modelo mental ou reduziria pela metade nosso espaço. Um número inteiro não assinado não apenas corresponde ao conceito, mas fornece duas vezes a resolução.

Da perspectiva do hardware, números inteiros não assinados são simples. Eles são provavelmente a estrutura de bits mais fácil de executar matemática. E, sem dúvida, poderíamos simplificar o hardware simulando tipos inteiros (ou mesmo ponto flutuante!) Em um compilador. Então, por que os números inteiros não assinados e assinados são implementados no hardware?

Bem ... desempenho!

É mais eficiente implementar números inteiros assinados no hardware do que no software. O hardware pode ser instruído para executar a matemática em qualquer tipo de número inteiro em uma única instrução. E isso é muito bom , porque o hardware esmaga os bits mais ou menos em paralelo. Se você tentar simular isso no software, o tipo inteiro que você escolher "simular" exigirá, sem dúvida, muitas instruções e será notavelmente mais lento.

svidgen
fonte
2
Nessa linha, você pode salvar uma operação ao fazer a verificação dos limites da matriz. Se você usar um número inteiro não assinado, precisará verificar apenas se o índice fornecido é menor que o tamanho da matriz (porque não pode ser negativo).
riwalk
2
@ dan04 Certamente pode ... Mas, se você estiver usando um int de incremento automático a partir de 0 ou 1, o que é uma prática bastante comum, você impediu o uso de metade dos números disponíveis. E embora você possa começar a contar com -2 ^ 31 (ou o que seja), você terá um caso potencial de "borda" no meio do espaço de identificação.
Svidgen
1
Cortar seu campo pela metade é meio que um argumento fraco. Provavelmente, se seu aplicativo exigir mais de 2 bilhões, também precisará de mais de 4 bilhões.
corsiKa
1
@corsiKa: por esse motivo, se requer mais de 4, provavelmente requer 8, depois 16, etc. Onde termina?
Whatsisname
1
@whatsisname geralmente, você usa tipos inteiros de 8, 16, 32 ou 64 bits. Dizer que não assinado é melhor porque você obtém todos os 32 bits, em vez do intervalo limitado de 31 bits de espaço inteiro positivo em um byte assinado, não vai importar muito na maioria dos casos.
corsiKa
9

Sua pergunta consiste em duas partes:

  1. Qual é o objetivo de números inteiros não assinados?

  2. Inteiros não assinados valem a pena?

1. Qual é o objetivo de números inteiros não assinados?

Números não assinados, simplesmente, representam uma classe de quantidades para as quais os valores negativos não têm sentido. Claro, você pode dizer que a resposta para a pergunta "quantas maçãs eu tenho?" pode ser um número negativo se você deve algumas maçãs a alguém, mas e a questão de "quanta memória eu tenho?" - você não pode ter uma quantidade negativa de memória. Portanto, números inteiros não assinados são muito adequados para representar essas quantidades e têm o benefício de poder representar o dobro do intervalo de valores positivos do que os números inteiros assinados. Por exemplo, o valor máximo que você pode representar com um número inteiro assinado de 16 bits é 32767, enquanto que com um número inteiro não assinado de 16 bits é 65535.

2. Os números inteiros não assinados valem a pena?

Inteiros não assinados realmente não representam nenhum problema, portanto, sim, valem a pena. Veja bem, eles não exigem um conjunto extra de "algoritmos"; o circuito necessário para implementá-los é um subconjunto do circuito necessário para implementar números inteiros assinados.

Uma CPU não possui um multiplicador para números inteiros assinados e um multiplicador diferente para números não assinados; possui apenas um multiplicador, que funciona de uma maneira ligeiramente diferente, dependendo da natureza da operação. O suporte à multiplicação assinada requer um pouco mais de circuito do que o não assinado, mas, como precisa ser suportado de qualquer maneira, a multiplicação não assinada vem praticamente de graça, está incluída no pacote.

Quanto à adição e subtração, não há nenhuma diferença nos circuitos. Se você ler a chamada representação de complemento dos dois, descobrirá que ela é projetada de maneira tão inteligente que essas operações podem ser executadas exatamente da mesma maneira, independentemente da natureza dos números inteiros.

A comparação também funciona da mesma maneira, uma vez que nada mais é do que subtrair e descartar o resultado, a única diferença está nas instruções de ramificação condicional (salto), que funcionam observando diferentes sinalizadores da CPU que são definidos pelo instrução anterior (de comparação). Nesta resposta: /programming//a/9617990/773113, você pode encontrar uma explicação de como eles funcionam na arquitetura Intel x86. O que acontece é que a designação de uma instrução de salto condicional como assinada ou não assinada depende de quais sinalizadores ela examina.

Mike Nakis
fonte
1
minha pergunta assumiu tudo isso, por algoritmo eu quis dizer que a regra para menos que maior que etc era diferente. O custo que vejo é ter muitas instruções extras. Se os programas de alto nível gostaria de ver dados como padrões de bits que pode ser facilmente implementado por exemplo por um compilador
JTW
3
@ jtw - mas o ponto é que essas instruções extras são realmente muito semelhantes às instruções necessárias para números assinados e quase todos os circuitos necessários para eles podem ser compartilhados . O custo extra da implementação dos dois tipos é quase zero.
Periata Respira
1
sim que responde a minha pergunta, acrescentando as instruções de desvio extra vem com um custo pequeno e muitas vezes são úteis na prática
JTW
1
"Operações não assinadas requerem um tratamento extra quando se trata de divisão e multiplicação" Eu acho que você tem isso ao contrário. A multiplicação e a divisão são mais fáceis com valores não assinados. O tratamento extra é necessário para lidar com operandos assinados.
Cody Gray
@CodyGray Eu sabia que alguém iria aparecer para dizer isso. Você está certo, é claro. Este é o raciocínio por trás da minha declaração, que originalmente omiti por uma questão de brevidade: uma CPU não poderia oferecer multiplicação e divisão apenas sem sinal, porque as versões assinadas são muito úteis. De fato, multiplicação e divisão assinadas são uma obrigação; não assinado são opcionais. Portanto, se não for oferecido também um sinal , isso pode ser visto como exigindo um pouco mais de circuito.
precisa
7

Microprocessadores são inerentemente não assinados. Os números assinados são a coisa implementada, e não o contrário.

Os computadores podem funcionar e funcionam bem sem números assinados, mas nós, humanos que precisamos de números negativos, daí a invenção foi inventada.

Pieter B
fonte
4
Muitos microprocessadores possuem instruções assinadas e não assinadas para várias operações.
Whatsisname
1
@ whatsisname: É o contrário: muitos microprocessadores possuem apenas instruções não assinadas. A poucos têm instruções assinados. Isso ocorre porque, com a aritmética com complemento 2s, o valor do bit é o mesmo, independentemente do clima, o número é assinado ou não e como a leitura do número é apenas uma questão de interpretação - portanto, é mais fácil implementá-lo como um recurso de compilador. Geralmente, apenas micros antigos que assumem que programadores não usam compiladores têm instruções assinadas sofisticadas para tornar o código de montagem legível.
slebetman
3

Porque eles têm mais um bit que está facilmente disponível para armazenamento e você não precisa se preocupar com números negativos. Não há muito mais do que isso.

Agora, se você precisar de um exemplo de onde você precisaria desse bit extra, há muito o que encontrar, se você procurar.

Meu exemplo favorito vem de placas de bit em motores de xadrez. Existem 64 quadrados em um tabuleiro de xadrez, portanto, unsigned longfornece armazenamento perfeito para uma variedade de algoritmos que giram em torno da geração de movimentos. Considerando o fato de que você precisa realizar operações binárias (bem como operações de deslocamento !!), é fácil ver por que é mais fácil não ter que se preocupar com o que acontece quando o MSB está definido. Isso pode ser feito com assinatura longa, mas é muito mais fácil usar sem assinatura.

riwalk
fonte
3

Tendo uma formação matemática pura, essa é uma abordagem um pouco mais matemática para qualquer pessoa interessada.

Se começarmos com um número inteiro assinado e sem sinal de 8 bits, o que temos é basicamente o número 256 do módulo inteiro, no que diz respeito à adição e multiplicação, desde que o complemento 2 seja usado para representar números inteiros negativos (e é assim que todo processador moderno faz isso) .

Onde as coisas diferem está em dois lugares: um são operações de comparação. Em certo sentido, o número inteiro do módulo 256 é melhor considerado um círculo de números (como o número inteiro do módulo 12 em um relógio analógico à moda antiga). Para fazer comparações numéricas (é x <y), precisamos decidir quais números são menores que os outros. Do ponto de vista do matemático, queremos incorporar os números inteiros módulo 256 no conjunto de todos os números de alguma forma. Mapear o número inteiro de 8 bits cuja representação binária é todos os zeros para o número 0 é a coisa mais óbvia a se fazer. Podemos então mapear outros para que '0 + 1' (o resultado de zerar um registro, digamos ax, e incrementá-lo por um, via 'inc ax') vá para o número inteiro 1, e assim por diante. Podemos fazer o mesmo com -1, por exemplo, mapeando '0-1' para o número inteiro -1 e '0-1-1' para o número inteiro -2. Devemos garantir que essa incorporação seja uma função, portanto, não é possível mapear um único número inteiro de 8 bits para dois números inteiros. Como tal, isso significa que, se mapearmos todos os números no conjunto de números inteiros, 0 estará lá, juntamente com alguns números inteiros menores que 0 e outros mais que 0. Existem essencialmente 255 maneiras de fazer isso com um inteiro de 8 bits (de acordo com para o mínimo desejado, de 0 a -255). Então você pode definir 'x <y' em termos de '0 <y - x'.

Existem dois casos de uso comuns, para os quais o suporte a hardware é sensato: um com todos os números inteiros diferentes de zero sendo maior que 0 e outro com uma divisão de aproximadamente 50/50 em torno de 0. Todas as outras possibilidades são facilmente emuladas pela conversão de números por meio de um acréscimo adicional. e sub 'antes das operações, e a necessidade disso é tão rara que não consigo pensar em um exemplo explícito no software moderno (já que você pode trabalhar com uma mantissa maior, digamos 16 bits).

A outra questão é a de mapear um número inteiro de 8 bits no espaço de números inteiros de 16 bits. -1 vai para -1? É isso que você deseja se 0xFF representar -1. Nesse caso, a extensão de sinal é a coisa mais sensata a ser feita, de modo que 0xFF vá para 0xFFFF. Por outro lado, se 0xFF deveria representar 255, você deseja que ele seja mapeado para 255, daí para 0x00FF, em vez de 0xFFFF.

Essa é a diferença entre as operações de 'turno' e 'turno aritmético' também.

Por fim, no entanto, tudo se resume ao fato de que int's em software não são números inteiros, mas representações em binário, e apenas alguns podem ser representados. Ao projetar o hardware, é necessário fazer escolhas sobre o que fazer nativamente no hardware. Como no complemento 2, as operações de adição e multiplicação são idênticas, faz sentido representar números inteiros negativos dessa maneira. Então é apenas uma questão de operações que dependem de quais números inteiros suas representações binárias devem representar.

John Allsup
fonte
Gosto da abordagem matemática, mas, em vez de pensar apenas na promoção para um tamanho maior específico, acho melhor generalizar em termos de operações em números binários de tamanho infinito. Subtraia 1 de qualquer número cujos k dígitos mais à direita sejam 0 e os k mais à direita do resultado serão 1, e pode-se provar por indução que, se alguém fizer matemática com um número infinito de bits, cada bit será 1. Para não assinado matemática, ignora-se todos, exceto os bits inferiores de um número.
Supercat
2

Vamos examinar o custo de implementação para adicionar números inteiros não assinados a um design de CPU com números inteiros assinados existentes.

Uma CPU típica precisa das seguintes instruções aritméticas:

  • ADD (que adiciona dois valores e define um sinalizador se a operação estourar)
  • SUB (que subtrai um valor de outro e define vários sinalizadores - discutiremos abaixo)
  • CMP (que é essencialmente 'SUB e descarta o resultado, mantenha apenas os sinalizadores')
  • LSH (deslocamento para a esquerda, defina um sinalizador em excesso)
  • RSH (deslocamento à direita, defina uma bandeira se um 1 for deslocado)
  • Variantes de todas as instruções acima que lidam com o transporte / empréstimo de sinalizadores, permitindo que você encadeie as instruções convenientemente para operar em tipos maiores do que os registros da CPU
  • MUL (multiplicar, definir sinalizadores etc. - não disponível universalmente)
  • DIV (dividir, definir sinalizadores, etc - muitas arquiteturas de CPU não possuem isso)
  • Mova de um tipo inteiro menor (por exemplo, 16 bits) para um maior (por exemplo, 32 bits). Para números inteiros assinados, isso geralmente é chamado de MOVSX (mover com extensão de sinal).

Ele também precisa de instruções lógicas:

  • Ramificar em zero
  • Ramificar em maior
  • Ramifique com menos
  • Ramo em excesso
  • Versões negadas de todos os itens acima

Para executar as ramificações acima em comparações com números inteiros assinados, a maneira mais fácil é fazer com que a instrução SUB defina os seguintes sinalizadores:

  • Zero. Defina se a subtração resultou em um valor zero.
  • Transbordar. Defina se a subtração pediu emprestado um valor do bit mais significativo.
  • Placa. Defina para o bit do sinal do resultado.

Em seguida, os ramos aritméticos são implementados da seguinte maneira:

  • Ramificar em zero: se o sinalizador zero estiver definido
  • Ramifique com menos: se o sinalizador de sinal for diferente do sinalizador de estouro
  • Ramificar em maior: se o sinalizador de sinalização for igual ao sinalizador de estouro e o sinalizador zero estiver limpo.

As negações devem seguir obviamente a maneira como elas são implementadas.

Portanto, seu design existente já implementa tudo isso para números inteiros assinados. Agora vamos considerar o que precisamos fazer para adicionar números inteiros não assinados:

  • ADD - a implementação do ADD é idêntica.
  • SUB - precisamos adicionar um sinalizador extra: o sinalizador de transporte é definido quando um valor é emprestado além do bit mais significativo do registro.
  • CMP - não muda
  • LSH - não muda
  • RSH - o deslocamento certo para valores assinados mantém o valor do bit mais significativo. Para valores não assinados, devemos defini-lo como zero.
  • MUL - se o seu tamanho de saída é o mesmo como entrada, sem tratamento especial é necessário (x86 faz ter tratamento especial, mas apenas porque tem saída em um par de registro, mas nota que esta facilidade é realmente muito raramente usado, então seria um candidato mais óbvio para deixar de fora do processador que os tipos não assinados)
  • DIV - não são necessárias alterações
  • Mover de um tipo menor para outro maior - é necessário adicionar o MOVZX, mover com extensão zero. Observe que o MOVZX é extremamente simples de implementar.
  • Ramificar em zero - inalterado
  • Ramifique em menos - pula quando carrega o conjunto de sinalizadores.
  • Ramifique em saltos maiores se carregar bandeira e zerar ambos livres.

Observe que, em cada caso, as modificações são muito simples e podem ser implementadas simplesmente ativando ou desativando uma pequena seção do circuito ou adicionando um novo registro de sinalizador que pode ser controlado por um valor que precisa ser calculado como parte de implementação da instrução de qualquer maneira.

Portanto, o custo de adicionar instruções não assinadas é muito pequeno . Por que isso deve ser feito , observe que os endereços de memória (e deslocamentos nas matrizes) são valores inerentemente não assinados. Como os programas gastam muito tempo manipulando endereços de memória, ter um tipo que os manipule corretamente facilita a gravação dos programas.

Periata Breatta
fonte
obrigado, isso responde minha pergunta, o custo é pequeno e as instruções são frequentemente úteis
jtw
1
A multiplicação não assinada de tamanho duplo é essencial ao executar aritmética de precisão múltipla e provavelmente é boa para uma melhoria de velocidade geral melhor que 2x no desempenho da criptografia RSA. Além disso, a divisão é diferente nos casos assinados e não assinados, mas como o caso não assinado é mais fácil e a divisão é rara o suficiente e lenta o suficiente para que adicionar algumas instruções não prejudique muito, a coisa mais simples a fazer seria implementar apenas a divisão não assinada e envolva-o com alguma lógica de manipulação de sinais.
Supercat
2

Os números não assinados existem em grande parte para lidar com situações em que é necessário um anel algébrico de quebra automática (para um tipo não assinado de 16 bits, seria o anel do número congruente mod 65536). Pegue um valor, adicione qualquer quantidade menor que o módulo e a diferença entre os dois valores será a quantidade que foi adicionada. Como um exemplo do mundo real, se um medidor de utilidade lê 9995 no início de um mês e um usa 23 unidades, o medidor lerá 0018 no final do mês. Ao usar um tipo de anel algébrico, não há necessidade de fazer algo especial para lidar com o estouro. Subtrair 9995 de 0018 produzirá 0023, precisamente o número de unidades que foram usadas.

No PDP-11, a máquina para a qual C foi implementada pela primeira vez, não havia tipos inteiros não assinados, mas os tipos assinados podiam ser usados ​​para aritmética modular que envolvia entre 32767 e -32768 em vez de entre 65535 e 0. As instruções de número inteiro plataformas não envolviam as coisas de maneira limpa; em vez de exigir que as implementações devem emular os números inteiros de complemento de dois usados ​​no PDP-11, a linguagem adicionou tipos não assinados que geralmente tinham que se comportar como anéis algébricos e permitiu que tipos inteiros assinados se comportassem de outras maneiras em caso de estouro.

Nos primeiros dias de C, havia muitas quantidades que podiam exceder 32767 (o comum INT_MAX), mas não 65535 (o comum UINT_MAX). Assim, tornou-se comum o uso de tipos não assinados para armazenar essas quantidades (por exemplo, size_t). Infelizmente, não há nada no idioma para distinguir entre tipos que devem se comportar como números com um pouco mais de alcance positivo do que tipos que devem se comportar como anéis algébricos. Em vez disso, a linguagem faz com que tipos menores que "int" se comportem como números, enquanto tipos de tamanho normal se comportam como anéis algébricos. Conseqüentemente, chamar funções como:

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

com (65535, 65535) terá um comportamento definido em sistemas com int16 bits (ou seja, retorno 1), um comportamento diferente com int33 bits ou mais (retorno 0xFFFE0001) e Comportamento indefinido em sistemas em que "int" esteja em qualquer lugar entre [note que o gcc irá normalmente produz resultados aritmeticamente corretos com resultados entre INT_MAX + 1u e UINT_MAX, mas às vezes gera código para a função acima que falha com esses valores!]. Não é muito útil.

Ainda assim, a falta de tipos que se comportam consistentemente como números ou consistentemente como um anel algébrico não altera o fato de que os tipos de anéis algébricos são quase indispensáveis ​​para alguns tipos de programação.

supercat
fonte