Por que preferir o complemento de dois em vez de sinal e magnitude para números assinados?

Só estou curioso se existe uma razão pela qual, para representar -1 em binário, o complemento de dois é usado: inverter os bits e adicionar 1?

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

Isenção de responsabilidade: não confio na aritmética binária para o meu trabalho!

Isso é feito para que a adição não precise ter nenhuma lógica especial para lidar com números negativos. Confira o artigo na Wikipedia .

Digamos que você tenha dois números, 2 e -1. Na sua maneira "intuitiva" de representar números, eles seriam 0010e 1001, respectivamente (estou usando 4 bits de tamanho). No caminho do complemento dos dois , eles são 0010e 1111. Agora, digamos que eu queira adicioná-los.

A adição do complemento de dois é muito simples. Você adiciona números normalmente e qualquer bit de transporte no final é descartado. Então, eles são adicionados da seguinte forma:

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

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

Mas no seu método "intuitivo", adicionar é mais complicado:

  0010
+ 1001
= 1011

Qual é -3, certo? A adição simples não funciona neste caso. Você precisa observar que um dos números é negativo e, se esse for o caso, use um algoritmo diferente.

Para esse método de armazenamento "intuitivo", a subtração é uma operação diferente da adição, exigindo verificações adicionais dos números antes que eles possam ser adicionados. Como você deseja que as operações mais básicas (adição, subtração, etc.) sejam o mais rápido possível, é necessário armazenar números de uma maneira que permita usar os algoritmos mais simples possíveis.

Além disso, no método de armazenamento "intuitivo", existem dois zeros:

0000  "zero"
1000  "negative zero"

Que são intuitivamente o mesmo número, mas têm dois valores diferentes quando armazenados. Todo aplicativo precisará executar etapas extras para garantir que valores diferentes de zero também não sejam negativos.

Há outro bônus em armazenar entradas dessa maneira, e é nesse momento que você precisa estender a largura do registro em que o valor está sendo armazenado. Com o complemento two, armazenar um número de 4 bits em um registro de 8 bits é uma questão de repetir sua bit mais significativo:

    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 pedaço de sinal da palavra menor e repeti-lo até preencher a largura da palavra maior.

Com seu método, você precisaria limpar o bit existente, que é uma operação extra além do preenchimento:

    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 4 bits extras nos dois casos, mas no caso "intuitivo", também é necessário limpar o quinto bit. É um pequeno passo extra em uma das operações mais fundamentais e comuns presentes em todos os aplicativos.

A Wikipedia diz tudo:

O sistema de complemento de dois tem a vantagem de não exigir que os circuitos de adição e subtração examinem os sinais dos operandos para determinar se devem ser adicionados ou subtraídos. Essa propriedade torna o sistema mais simples de implementar e capaz de lidar facilmente com aritmética de maior precisão. Além disso, o zero tem apenas uma única representação, obviando as sutilezas associadas ao zero negativo, que existem nos sistemas de complemento de um.

Em outras palavras, adicionar é o mesmo, independentemente de o número ser negativo.

Mesmo que essa pergunta seja antiga, deixe-me colocar meus 2 centavos.

Antes de explicar isso, vamos voltar ao básico. O complemento 2 'é o complemento de 1 + 1. Agora, o que é o complemento do 1 e qual é o seu significado além disso.

A soma de qualquer número de n bits e seu complemento de 1 fornece o número mais alto possível que pode ser representado por esses 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 acontecerá se tentarmos adicionar mais 1 ao resultado. Isso resultará em um estouro.

O resultado será 1 00000 (como estamos trabalhando com números de 4 bits (o 1 à esquerda é um estouro)

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 então decidiu chamar o complemento de 1 + 1 como complemento de 2 '. Portanto, 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)

Tudo isso gera mais uma pergunta: por que podemos usar apenas o (n-1) dos n bits para representar o número positivo e por que o n-ésimo bit esquerdo representa o sinal (0 no bit mais à esquerda significa + número de ve e 1 significa -ve número). por exemplo, por que usamos apenas os primeiros 31 bits de um int em java para representar um número positivo se o 32º bit é 1, seu número -ve.

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

1 0000 (resultado é zero, com o carry 1 transbordando)

Assim, o sistema de (n + 2'complemento de n) = 0 ainda funciona. A única ambiguidade aqui é o complemento de 2 de 12 é 0100 que ambiguamente também representa +8, além de representar -12 no sistema de complemento de 2s.

Esse problema será resolvido se os números positivos sempre tiverem um 0 no bit esquerdo. Nesse caso, o complemento de 2 deles sempre terá um 1 no bit esquerdo mais e não teremos a ambiguidade do mesmo conjunto de bits que representa o número de complemento de 2 e também o número + ve.

O complemento de Two permite que a adição e a subtração sejam feitas da maneira normal (como você procura por números não assinados). Também impede -0 (uma maneira separada de representar 0 que não seria igual a 0 no método bit a bit normal de comparação de números).

isso é para simplificar somas e diferenças de números. uma soma de um número negativo e um positivo codificado nos complementos de 2 é o mesmo que resumi-los da maneira normal.

A implementação usual da operação é "inverter os bits e adicionar 1", mas há outra maneira de defini-la que provavelmente torna a lógica mais clara. O complemento de 2 é a forma que você obtém se usar a representação não assinada usual, em que cada bit controla a próxima potência de 2 e apenas tornar negativo o termo mais significativo.

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

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

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

Nenhum dos outros bits muda de significado, e carregar para o ₇ é "transbordar" e não se espera que funcione; portanto, praticamente todas as operações aritméticas funcionam sem modificação (como outros observaram). A magnitude do sinal geralmente inspeciona o bit do sinal e usa uma lógica diferente.

O complemento de dois permite que números negativos e positivos sejam adicionados sem nenhuma lógica especial.

Se você tentou adicionar 1 e -1 usando o método
10000001 (-1)
+00000001 (1),
obtém
10000010 (-2)

Em vez disso, usando o complemento de dois, podemos adicionar

11111111 (-1)
+00000001 (1) você obtém
00000000 (0)

O mesmo vale para subtração.

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

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

Para expandir outras respostas:

No complemento de dois

• Adicionar é o mesmo mecanismo que adicionar números inteiros positivos.
• Subtrair também não muda
• Multiplicação também!

A divisão requer um mecanismo diferente.

Tudo isso é verdade porque o complemento de dois é apenas uma aritmética modular normal, onde escolhemos olhar alguns números como negativos subtraindo o módulo.

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

O complemento 2 de 0100 (4) será 1100. Agora 1100 é 12, se digo normalmente. Então, quando digo 1100 normal, então é 12, mas quando digo o complemento de 2 1100, então é -4? Além disso, em Java, quando 1100 (vamos assumir 4 bits por enquanto) é armazenado, então como é determinado se é +12 ou -4 ?? - hagrawal 02/07 às 16:53

Na minha opinião, a pergunta feita neste comentário é bastante interessante e, portanto, gostaria de reformulá-lo e depois fornecer uma resposta e um exemplo.

PERGUNTA - Como o sistema pode estabelecer como um ou mais bytes adjacentes devem ser interpretados? Em particular, como o sistema pode estabelecer se uma determinada sequência de bytes é um número binário simples ou um número complementar de 2?

RESPOSTA - O sistema estabelece como interpretar uma sequência de bytes por meio de tipos. Tipos definem

• quantos bytes precisam ser considerados
• como esses bytes precisam ser interpretados

EXEMPLO - Abaixo assumimos que

• chartem 1 byte de comprimento
• shorttem 2 bytes de comprimento
• int's e float' s têm 4 bytes de comprimento

Observe que esses tamanhos são específicos para o meu sistema. Embora bastante comuns, eles podem ser diferentes de sistema para sistema. Se você estiver curioso sobre o que eles estão no seu sistema, use o operador sizeof .

Primeiro, definimos uma matriz contendo 4 bytes e inicializamos todos eles para o número binário 10111101, correspondente ao número hexadecimal BD.

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

Em seguida, lemos o conteúdo do array usando diferentes tipos.

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, intefloat

// 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 na RAM ( l_Just4Bytes[ 0..3 ]) sempre permanecem exatamente iguais. A única coisa que muda é como os interpretamos.

Mais uma vez, vamos dizer ao sistema como interpretá-los através de tipos .

Por exemplo, acima, usamos os seguintes tipos para interpretar o conteúdo da l_Just4Bytesmatriz

• unsigned char: 1 byte em binário comum
• signed char: 1 byte no complemento de 2
• unsigned short: 2 bytes em notação binária simples
• short: 2 bytes no complemento de 2
• unsigned int: 4 bytes em notação binária simples
• int: 4 bytes no complemento de 2
• float: 4 bytes na notação de precisão única IEEE 754

[EDIT] Esta postagem foi editada após o comentário pelo usuário4581301. Obrigado por reservar um tempo para soltar essas poucas linhas úteis!

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

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

Se houver x bits, o complemento de dois variará de + (2 ^ x / 2 + 1) a - (2 ^ x / 2). O complemento de alguém será executado de + (2 ^ x / 2) a - (2 ^ x / 2), mas permitirá um zero negativo (0000 é igual a 1000 em um sistema de complemento de 4 bits 1).

Bem, sua intenção não é realmente reverter todos os bits do seu número binário. Na verdade, é para subtrair cada dígito de 1. É apenas uma coincidência feliz que subtrair 1 de 1 resulta em 0 e subtrair 0 de 1 resulta em 1. Portanto, trocar bits está efetivamente realizando essa subtração.

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

Isso explica o primeiro passo no cálculo do complemento de dois. Agora vamos incluir o segundo passo - adicionando 1 - também na imagem.

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

11111111 - 10110001 + 1

O que você ganha? Este:

100000000 - 10110001

Esta é a equação final. E, executando essas duas etapas, você está tentando encontrar essa diferença final: o número binário subtraído de outro número binário com um dígito extra e contendo zeros, exceto na posição do bit de maior significado.

Mas por que estamos realmente buscando essa diferença? Bem, daqui em diante, acho que seria melhor se você ler o artigo da Wikipedia .

Realizamos apenas operações de adição para adição e subtração. Nós adicionamos o segundo operando ao primeiro operando para adição. Para subtração, adicionamos o complemento 2 do segundo operando ao primeiro operando.

Com a representação do complemento de 2's, não precisamos de componentes digitais separados para subtração - apenas somadores e complementadores são usados.

Vale a pena notar que em algumas máquinas de adição antigas, antes dos dias dos computadores digitais, a subtração seria realizada com o operador digitando valores usando um conjunto de legendas de cores diferentes em cada tecla (para que cada tecla digitasse nove menos o número a ser subtraído) e pressionar um botão especial assumiria uma transferência para um cálculo. Assim, em uma máquina de seis dígitos, para subtrair 1234 de um valor, o operador pressionaria teclas que normalmente indicariam "998.765" e pressionaria um botão para adicionar esse valor mais um ao cálculo em andamento. A aritmética do complemento de dois é simplesmente o equivalente binário da aritmética anterior do "complemento de dez".

A vantagem de realizar subtração pelo método complemento é a redução da
complexidade do hardware. Não há necessidade de diferentes circuitos digitais para adição e subtração.

Uma grande vantagem da representação do complemento de dois que ainda não foi mencionada aqui é que os bits inferiores da soma, diferença ou produto de um complemento de dois dependem apenas dos bits correspondentes dos operandos. A razão pela qual o valor assinado de 8 bits para -1 é 11111111que subtrair qualquer número inteiro cujos 8 bits mais baixos sejam 00000001de qualquer outro número cujos 8 bits mais baixos são 0000000resultará em um número inteiro cujos 8 bits mais baixos são11111111. Matematicamente, o valor -1 seria uma sequência infinita de 1s, mas todos os valores dentro do intervalo de um tipo inteiro específico serão todos os 1s ou todos os 0 após um determinado ponto; portanto, é conveniente que os computadores "estendam" o número mais significativo, como se representasse um número infinito de 1 ou 0.

O complemento de dois é praticamente a única representação de número assinado que funciona bem ao lidar com tipos maiores que o tamanho natural das palavras de uma máquina binária, pois ao executar adição ou subtração, o código pode buscar o menor pedaço de cada operando, calcular o menor pedaço de o resultado e armazene-o e, em seguida, carregue o próximo pedaço de cada operando, calcule o próximo pedaço do resultado e armazene-o etc. Assim, mesmo um processador que requer que todas as adições e subtrações passem por um único registro de 8 bits pode lidar com números assinados de 32 bits razoavelmente eficientemente (mais lentamente do que com um registrador de 32 bits, é claro, mas ainda assim viável).

Ao usar qualquer outra representação assinada permitida pelo Padrão C, todo bit do resultado pode ser afetado por qualquer bit dos operandos, tornando necessário manter um valor inteiro nos registros de uma só vez ou seguir os cálculos com um extra etapa que exigiria, pelo menos em alguns casos, a leitura, modificação e reescrita de cada parte do resultado.

Existem diferentes tipos de representações:

1. representação numérica não assinada
2. representação de número assinado
3. representação de complemento de alguém
4. Representação do complemento de dois

Representação de número não assinado usada para representar apenas números positivos

Representação de número assinado usado para representar um número positivo e um negativo. Em representação de número assinado, o bit MSB representa o bit de sinal e os bits restantes representam o número. Quando MSB é 0 significa que o número é positivo e Quando MSB é 1 significa que o número é negativo.

O problema com a representação do número assinado é que existem dois valores para 0.

O problema com a representação de complemento de alguém é que existem dois valores para 0.

Mas se usarmos a representação do complemento de Dois, haverá apenas um valor para 0, e é por isso que representamos números negativos na forma de complemento de dois.

Fonte: Por que os números negativos são armazenados no formato de complemento de dois bytes de digigabytes

Uma resposta satisfatória do motivo pelo qual o Complemento Two2 é usado para representar números negativos, em vez do sistema Complemento da One, é que o sistema Complemento da Two resolve o problema de múltiplas representações de 0 e a necessidade de transporte final existente no sistema de complemento One da representação negativa. números.

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

Para o transporte ao redor, visite https://en.wikipedia.org/wiki/End-around_carry