Números negativos em binário
Até agora falámos de inteiros positivos e de como estes são representados nas máquinas. No entanto, por vezes precisamos de lidar também com números negativos. Como é que são representados nos computadores?
Já vimos que o número 1 é representado como
0001 em binário, o número 6 como 0110, etc. O zero é representado por todos os bits a zero, isto é, 0000. Uma forma simples de armazenar números negativos é reservar um bit “especial” que indique se o número é negativo. Assim, esse bit seria 1 caso o número fosse negativo e 0 caso contrário. E é exatamente desta forma que a maioria dos computadores trata números negativos. Eles atribuem um bit especial, o mais à esquerda da representação binária, para 1 se o número for negativo ou 0 se for positivo.Existe, contudo, um detalhe adicional além de simplesmente definir 1 como o primeiro bit da representação binária. Na representação decimal (os números do nosso dia a dia, como 4, 5, 10, 311, etc.), números positivos e negativos anulam-se mutuamente. Se somarmos 6 e -6, obtemos 0. Essa propriedade não pode ser perdida no binário. Isto significa que se somarmos 6 e -6 em binário, também devemos obter 0.
Para imaginar isso, suponhamos que temos 4 bits para representar um número e 1 bit adicional para armazenar o sinal. Portanto, no total, são 5 bits. Assim, o 6 seria representado em binário como
00110, enquanto o 0 aparece como 00000. A representação de -6 deve ser o oposto de 6 para que a soma resulte em 0. Antecipando um pouco, a representação de -6 seria 11010. Se somarmos 00110 e 11010 em binário, o resultado será 00000.Para alternar entre positivo e negativo (e vice-versa) em binário, podemos usar um truque simples: invertem-se todos os bits (todos os 0 passam a 1 e todos os 1 passam a 0) e depois soma-se 1 ao resultado.
x = 6 # 00110
x = ~x + 1 # Inverte todos os bits e soma 1 => -6
x = ~x + 1 # Inverte todos os bits e soma 1 => 6
z = 0 # 00000
z = ~z + 1 # Inverte e +1 => 0
z = ~z + 1 # Inverte e +1 => 0
z = ~z # -1 (todos os bits a 1 na representação binária)
z = ~z # 0 (todos os bits a 0 na representação binária)Repare que a adição de números em binário funciona do mesmo modo que a adição em decimal: do dígito menos significativo para o mais significativo, levando em conta o carry (quando há transporte de um dígito para o seguinte).
Consoante a linguagem e a forma como é implementada, os computadores armazenam números de maneiras diferentes. Linguagens como C++ e Java têm tipos distintos para diferentes limites de valores. O tipo
int, por exemplo, armazena inteiros em 32 bits: 31 bits para o número e o bit frontal para o sinal ⇒ isto permite valores entre -2,147,483,648 () e 2,147,483,647 (). Note que o limite positivo é menor por 1. Isto acontece porque os valores positivos começam com o bit de sinal a 0, e o primeiro número que começa com 0 é o próprio 0 (todos os bits a zero).Desafio
Na terra mágica dos 7s, tudo está relacionado com o número 7. Nesta terra, os cientistas da computação desenvolveram um sistema em que os números binários (positivos e negativos) são armazenados em 77 bits.
Dado um bit-string
b, a tarefa é calcular o valor negativo desse número e representá-lo em 77 bits.Entrada
A entrada contém uma única linha que representa o bit-string
b (1 ≤ |b| ≤ 77). Pode representar tanto um número positivo como um número negativo.Saída
A saída deve conter uma linha que representa
-b com comprimento de 77 bits.Exemplos
Entrada | Saída |
1 | 11111111111111111111111111111111111111111111111111111111111111111111111111111 |
11111111111111111111111111111111111111111111111111111111111111111111111111111 | 00000000000000000000000000000000000000000000000000000000000000000000000000001 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB