Por que preferem complemento de dois mais sign-and-magnitude para os números assinados?

https://stackoverflow.com/questions/1125304

13-09-2019
|

Pergunta

Eu sou apenas curioso para saber se há uma razão pela qual, a fim de representar -1 em binário, complemento de dois é utilizado:? Invertendo os bits e adicionando 1

-1 é representado por 11.111.111 (complemento de dois) em vez de (para mim mais intuitivo) 10000001, que é binário 1 com o primeiro bit de flag negativo.

Disclaimer: Eu não dependem de aritmética binária para o meu trabalho

Solução

É feito de modo que a adição não precisa ter qualquer lógica especial para lidar com números negativos. Confira o artigo sobre Wikipedia .

Digamos que você tenha dois números, 2 e -1. Em seu caminho "intuitiva" de representar números, eles seriam 0010 e 1001, respectivamente (eu estou aderindo a 4 bits para o tamanho). Em forma de complemento de dois, eles são 0010 e 1111. Agora, vamos dizer que eu quero adicioná-los.

Além de complemento de dois é muito simples. Você adicionar números normalmente e qualquer carry no final é descartado. Então, eles estão adicionado como se segue:

  0010
+ 1111
=10001
= 0001 (discard the carry)

0001 é 1, que é o resultado esperado de "2 + (- 1)"

Mas em seu método "intuitiva", acrescentando é mais complicado:

  0010
+ 1001
= 1011

Qual é -3, certo? Além simples não funciona neste caso. Você precisa notar que um dos números é negativo e usar um algoritmo diferente se esse for o caso.

Para este método de armazenamento "intuitiva", subtracção é uma operação diferente do que a adição, exigindo verificações adicionais sobre os números antes que eles possam ser adicionados. Desde que você quer as operações mais básicas (adição, subtração, etc) para ser o mais rápido possível, você precisa armazenar números de uma forma que permite que você use os algoritmos mais simples possível.

Além disso, no método de armazenamento "intuitiva", há dois zeros:

0000  "zero"
1000  "negative zero"

O que são intuitivamente o mesmo número, mas têm dois valores diferentes quando armazenado. Cada aplicação terá de tomar medidas adicionais para garantir que valores não-zero também não são zero negativo.

Há um outro bônus com armazenar ints desta maneira, e isso é quando você precisa estender a largura do registrar o valor está sendo armazenado. Com complemento de dois, armazenar um número de 4 bits num registo de 8 bits é uma questão de repetir a sua parte mais significativa:

    0001 (one, in four bits)
00000001 (one, in eight bits)
    1110 (negative two, in four bits)
11111110 (negative two, in eight bits)

É apenas uma questão de olhar para o bit de sinal da palavra menor e repeti-lo até que ele almofadas a largura da palavra maior.

Com o seu método você precisa limpar o bit existente, que é uma operação adicional, além de padding:

    0001 (one, in four bits)
00000001 (one, in eight bits)
    1010 (negative two, in four bits)
10000010 (negative two, in eight bits)

Você ainda precisa definir os extras 4 bits em ambos os casos, mas no caso "intuitiva" você precisa limpar o 5º pouco também. É um pequeno passo extra em um dos a maioria das operações fundamentais e comuns presentes em cada aplicação.

Outras dicas

Wikipedia diz tudo:

O sistema de complemento de dois tem a vantagem de não exigir que a adição e subtração circuitos examinar os sinais dos operandos para determinar se deve adicionar ou subtrair. Esta propriedade torna o sistema mais simples de implementar e capaz de lidar facilmente maior precisão aritmética. Além disso, zero tem apenas uma única representação, obviando as subtilezas associados com negativo zero, o que existe em sistemas ones'-complemento.

Em outras palavras, adicionando é o mesmo, tempo ou não o número for negativo.

Mesmo que esta questão é antiga, deixe-me colocar em meus 2 centavos.

Antes de me explicar isso, vamos voltar ao básico. 2' complemento é um complemento + 1. Agora, o que é complemento de 1 e qual a sua importância, além disso.

Soma de qualquer número de n bits e seu complemento de 1 dá-lhe o maior número possível que pode ser representado por aqueles n-bits. Exemplo:

 0010 (2 in 4 bit system)
+1101 (1's complement of 2)
___________________________
 1111  (the highest number that we can represent by 4 bits)

Agora o que vai acontecer se tentarmos adicionar mais 1 ao resultado. Vai resulta em um estouro.

O resultado será 1 0000 que é 0 (como estamos trabalhando com 4 números bit, (o 1 à esquerda é um overflow)

Assim,

Any n-bit number + its 1's complement = max n-bit number
Any n-bit number + its 1'complement + 1 = 0 ( as explained above, overflow will occur as we are adding 1 to max n-bit number)

Alguém decidiu, então, chamada 1 do complemento + 1 como 2'complement. Assim, a afirmação acima se torna: Qualquer número n'bit + seu complemento de 2 = 0 o que significa complemento de 2 de um número = - (desse número)

Todos estes rendimentos mais uma pergunta, por que é que podemos utilizar apenas o (n-1) dos n bits para representar número positivo e por que o bit mais enésimo esquerda representam sinal (0 sobre os meios mais à esquerda bit + ve número, e 1 significa -ve número). por exemplo, por que nós usamos apenas os primeiros 31 bits de um int em java para representar número positivo se o bit 32 é 1, é um número ve.

 1100 (lets assume 12 in 4 bit system)
+0100(2's complement of 12)
___________________________

1 0000 (resultado é zero, com a transportar um transbordamento)

Assim, o sistema de (n + 2'complement de n) = 0, ainda funciona. A única ambigüidade aqui é complemento de 12 2 de é 0100 que ambiguamente também representa +8, que não representando -12 em 2s sistema complemento.

Este problema será resolvido se os números positivos têm sempre um 0 em sua maioria pouco à esquerda. Nesse caso, o complemento de 2 terá sempre um 1 em sua maioria pouco à esquerda, e nós não vamos ter a ambigüidade do mesmo conjunto de bits representando número de complemento a 2 de bem como um + ve número.

complemento de dois permite a adição e subtração de ser feito de uma forma normal (como você ferida para números não assinados). Isso também evita -0 (uma forma separada para representar 0 que não seria igual a 0 com o método normal de bit-a-bit de comparação de números).

Este é simplificar somas e diferenças de números. uma soma de um número negativo e um positivo codificada em 2 de complementos é o mesmo que soma-los da maneira normal.

A implementação usual da operação é "inverter os bits e adicionar 1", mas não há outra maneira de defini-lo de que, provavelmente, faz a razão mais clara. 2 do complemento é a forma que você começa se você tomar a representação sem sinal de costume, onde cada bit controles a próxima potência de 2, e apenas fazer o negativo termo mais significativo.

Tendo um valor de 8 bits ₇ ₆ ₅ ₄ ₃ ₂ ₁ ₀

A interpretação usual sem assinatura binário é:
2 ⁷ * ₇ + 2 ⁶ * ₆ + 2 ⁵ * ₅ + 2 ⁴ * ₄ + 2 ³ * ₃ + 2 ² * ₂ + 2 ¹ * ₁ + 2 ⁰ * um ₀
11111111 = + 64 + 128 32 + 16 + 8 + 4 + 2 + 1 = 255

A interpretação de complemento de dois é:
-2 ⁷ * ₇ + 2 ⁶ * ₆ + 2 ⁵ * ₅ + 2 ⁴ * ₄ + 2 ³ * ₃ + 2 ² * ₂ + 2 ¹ * ₁ + 2 ⁰ * a ₀
11111111 = + 64 + -128 32 + 16 + 8 + 4 + 2 + 1 = -1

Nenhum dos outros bits mudam de significado em tudo, e levando em um ₇ é "estouro" e não se espera que trabalho, por isso praticamente todas as operações aritméticas trabalhar sem modificação (como outros têm notado). Sign-magnitude inspecionar geralmente o bit de sinal e usar a lógica diferente.

complemento de dois permite que os números negativos e positivos a serem adicionados em conjunto, sem qualquer lógica especial.

Se você tentou adicionar 1 e -1 usando seu método
10000001 (-1)
+00000001 (1)
você começa
10000010 (-2)

Em vez disso, usando complemento de dois, podemos adicionar

11111111 (-1)
+00000001 (1) você começa
00000000 (0)

O mesmo é verdadeiro para subtração.

Além disso, se você tentar subtrair 4 de 6 (dois números positivos) pode complemento para 2 4 e adicionar os dois juntos 6 + (-4) = 6-4 = 2

Isto significa que subtração e adição de ambos números positivos e negativos podem ser feitas pelo mesmo circuito na CPU.

Para expandir em outras respostas:

Em dois complemento

A adição é o mesmo mecanismo inteiros positivos simples adição.
não Subtraindo não mudar também
A multiplicação também!

Divisão requer um mecanismo diferente.

Todos estes são verdadeiras porque complemento de dois é aritmética modular apenas normal, onde podemos escolher olhar para alguns números como negativo subtraindo o modulo.

Lendo as respostas para essa pergunta, me deparei com este comentário [editado].

2 de complemento de 0100 (4) será 1100. Agora 1100 é 12 se eu disser normalmente. Então, quando digo normais 1100, então é 12, mas quando eu digo 2 de complemento de 1100, em seguida, é -4? Além disso, em Java, quando 1100 (vamos supor 4 bits para agora) é armazenado, em seguida, Como é determinado se é 12 ou -4 ?? - hagrawal 02 de julho em 16:53

Na minha opinião, a pergunta feita neste comentário é bastante interessante e assim que eu gostaria em primeiro lugar para reformulá-la e, em seguida, para fornecer uma resposta e um exemplo.

PERGUNTA - Como o sistema pode estabelecer como bytes um ou mais adjacente têm de ser interpretados? Em particular, como pode o sistema de estabelecer se uma dada sequência de bytes é um número binário simples ou número de complemento a 2 de?

RESPOSTA - O sistema estabelece como interpretar uma seqüência de bytes através de tipos. Tipos definir

quantos bytes têm de ser consideradas
como esses bytes têm de ser interpretados

Exemplo - A seguir assumimos que

O char são 1 byte
O short são 2 bytes de comprimento
int do e do float são 4 bytes

Por favor, note que estes tamanhos são específicos para o meu sistema. Apesar de bastante comum, eles podem ser diferentes de sistema para sistema. Se você está curioso sobre o que eles estão no seu sistema, use o sizeof operador .

Em primeiro lugar, definir uma matriz contendo 4 bytes e inicializar todos eles para o número 10111101 binária, correspondente ao número hexadecimal BD.

// BD(hexadecimal) = 10111101 (binary)
unsigned char   l_Just4Bytes[ 4 ]   =   { 0xBD, 0xBD, 0xBD, 0xBD };

Em seguida, ler o conteúdo matriz usando tipos diferentes.

`unsigned char` e `signed char`

// 10111101 as a PLAIN BINARY number equals 189
printf( "l_Just4Bytes as unsigned char  -> %hi\n", *( ( unsigned char* )l_Just4Bytes ) );

// 10111101 as a 2'S COMPLEMENT number equals -67
printf( "l_Just4Bytes as signed char    -> %i\n", *( ( signed char* )l_Just4Bytes ) );

`unsigned short` e `short`

// 1011110110111101 as a PLAIN BINARY number equals 48573
printf( "l_Just4Bytes as unsigned short -> %hu\n", *( ( unsigned short* )l_Just4Bytes ) );

// 1011110110111101 as a 2'S COMPLEMENT number equals -16963
printf( "l_Just4Bytes as short          -> %hi\n", *( ( short* )l_Just4Bytes ) );

`unsigned int`, `int` e `float`

// 10111101101111011011110110111101 as a PLAIN BINARY number equals 3183328701
printf( "l_Just4Bytes as unsigned int   -> %u\n", *( ( unsigned int* )l_Just4Bytes ) );

// 10111101101111011011110110111101 as a 2'S COMPLEMENT number equals -1111638595
printf( "l_Just4Bytes as int            -> %i\n", *( ( int* )l_Just4Bytes ) );

// 10111101101111011011110110111101 as a IEEE 754 SINGLE-PRECISION number equals -0.092647
printf( "l_Just4Bytes as float          -> %f\n", *( ( float* )l_Just4Bytes ) );

Os 4 bytes de RAM (l_Just4Bytes[ 0..3 ]) permanecer sempre exatamente o mesmo. A única coisa que muda é a forma como interpretá-los.

Mais uma vez, que dizer ao sistema de como para interpretá-las através de tipos .

Por exemplo, acima temos utilizados os seguintes tipos de interpretar o conteúdo da matriz l_Just4Bytes

unsigned char: 1 byte no binário simples
signed char: 1 byte em complemento para 2
unsigned short: 2 bytes de binário simples notação
short: 2 bytes em 2 de complemento
unsigned int: 4 bytes em binário simples notação
int: 4 bytes em 2 de complemento
float: 4 bytes em IEEE 754 de precisão simples notação

[EDIT] Este post foi editado após o comentário de user4581301. Obrigado por tomar o tempo para soltar aquelas poucas linhas votos!

Você pode assistir Professor Jerry Cain de Stanford explicando o complemento de dois, na segunda palestra (a explicação sobre o 2 de começos do complemento por volta das 13:00) na série de palestras chamado de programação Paradigmas disponível para assistir a partir do canal YouTube da Standford. Aqui está o link para a série de palestras: http://www.youtube.com/view_play_list?p= 9D558D49CA734A02 .

complemento de dois é usado porque é mais simples de implementar em circuitos e também não permite que um negativo zero.

Se houver x pedaços, complemento de dois irá variar de + (2 ^ x / 2 + 1) para - (2 ^ x / 2). Um complemento será executado a partir + (2 ^ x / 2) para -. (2 ^ x / 2), mas permitirá um negativo zero (0000 é igual a 1000 em um 4 bits do sistema complemento de 1)

Bem, sua intenção não é realmente para reverter todos os bits do seu número binário. É realmente para subtrair cada seu dígito de 1. É apenas uma feliz coincidência que subtrair 1 de 1 resultados em 0 e subtraindo 0 de 1 resultados em 1. Assim pedaços lançando é efetivamente realizar esta subtração.

Mas por que você está encontrando diferença de cada dígito a partir de 1? Bem, você não é. Sua intenção real é calcular diferença do dado de número binário de outro número binário que tem o mesmo número de dígitos, mas contém apenas 1 de. Por exemplo, se o seu número é 10110001, quando você virar todos esses bits, você está computando efetivamente (11111111 - 10110001).

Isso explica o primeiro passo no cálculo do complemento de dois. Agora vamos incluir o segundo passo - a adição de 1 -. Também na imagem

Adicione 1 ao acima equação binária:

11111111 - 10110001 + 1

O que você ganha? Isto:

100000000 - 10110001

Esta é a equação final. E, exercendo essas duas etapas que você está tentando encontrar este, diferença final:. O número binário subtraído outro número binário com um dígito extra e contendo zeros, exceto na posição mais significação pouco

Mas por que estamos hankerin após essa diferença realmente? Bem, a partir de agora, eu acho que seria melhor se você ler o Wikipedia artigo .

Realizamos única operação de adição tanto para adição e subtração. Nós adicionamos o segundo operando ao primeiro operando para adição. Para subtração somarmos complemento do segundo operando a 2 de para o primeiro operando.

Com representação de complemento a 2 de nós não precisamos separar componentes digitais para somadores só de subtração e complementadores são utilizados.

É interessante notar que em algumas máquinas de somar mais cedo, antes dos dias de computadores digitais, subtração seria realizada por ter o operador introduzir valores usando um conjunto de cor diferente das lendas em cada tecla (de modo que cada chave iria entrar nove menos o número a ser subtraído), e pressionar um botão especial que assumiria uma bagagem em um cálculo. Assim, em uma máquina de seis dígitos, subtrair 1234 de um valor, o operador teria atingido chaves que normalmente indicam "998765" e apertar um botão para adicionar esse valor, mais um para o cálculo em andamento. aritmética de complemento de dois é simplesmente o equivalente binário do que anteriormente "ten's-complemento" aritmética.

A vantagem de realizar a subtração pelo método complemento é redução do hardware
complexity.The são nenhuma necessidade dos diferentes circuito digital para adição e subtraction.both adição e subtração são realizadas por víbora somente.

Uma grande vantagem da representação complemento de dois, que ainda não tenha sido mencionado aqui é que os bits mais baixos de uma soma, diferença, ou produto complemento de dois são dependentes única sobre os bits correspondentes de os operandos. A razão pela qual o valor de sinal de 8 bit para -1 é 11111111 é que subtraindo qualquer inteiro cujo mais baixas de 8 bits são 00000001 a partir de qualquer outro número inteiro cujo mais baixas de 8 bits são 0000000 irá produzir um número inteiro cujo mais baixas de 8 bits são 11111111. Matematicamente, o valor -1 seria uma seqüência infinita de 1s, mas todos os valores dentro do intervalo de um tipo inteiro particular será ou todos os 1 de ou todos os 0 de passado um certo ponto, por isso é conveniente para computadores "sign-estender" o o bit mais significativo de um número como se representado um número infinito de 1s ou 0s.

complemento de dois é apenas sobre a única representação número assinado que funciona bem quando se lida com os tipos maiores do tamanho da palavra natural de uma máquina binária, já que ao realizar adição ou subtração, código pode buscar o menor pedaço de cada operando, calcular o menor pedaço do resultado, e armazenar que, em seguida, carregar o próximo pedaço de cada operando, computar o próximo pedaço do resultado, e que loja, etc. Assim, mesmo um processador que exige que todas as adições e subtracções para passar por um único 8 bit registar pode lidar com números assinado de 32 bits razoavelmente eficiente (mais lento do que com um registo de 32 bits, é claro, mas ainda viável).

Ao usar das quaisquer outras representações assinados permitidos pelo C Padrão, cada bit do resultado poderia ser afetado por qualquer bit dos operandos, tornando-se necessário quer realizar um valor inteiro em registros de uma vez ou computações seguem outra pessoa com uma etapa extra que, pelo menos em alguns casos, exigem a leitura, modificação e reescrever cada pedaço do resultado.

Uma resposta satisfatória do porquê de Complemento de two2 é usado para representar números negativos em vez de sistema de Complemento de Uma delas é que resolve sistema de complemento de dois o problema da múltiplas representações de 0 e a necessidade de end-around-carry que existem no seu sistema de complemento de representar números negativos.

Para mais informações visite https://en.wikipedia.org/wiki/Signed_number_representations

Para-around-carry End Visita https://en.wikipedia.org/wiki/End-around_carry

porque os fabricantes de CPU são! Preguiçoso

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow

Por que preferem complemento de dois mais sign-and-magnitude para os números assinados?

unsigned char e signed char

unsigned short e short

unsigned int, int e float

`unsigned char` e `signed char`

`unsigned short` e `short`

`unsigned int`, `int` e `float`