Negative numbers in binary
So far we’ve talked about positive integers and how they’re represented in our machines. Yet, sometimes we need to work with negative numbers as well. How are they represented in the computers?
We’ve seen that the number 1 is represented as
0001 in binary, number 6 is represented as 0110, etc. 0 is represented as all zeros 0000. A logical trick we can do to store negative numbers is by keeping a “special” bit which would represent whether or not the number is negative. So, it would be 1 if the number is negative and 0 otherwise. And that’s exactly how most computers operate with negative numbers. They just have a special bit at the very left of the binary representation which is set to 1 if the number is negative and is set to 0 if it’s a positive one. There is a bit more to it than just having 1 as the first bit in the binary representation. In decimal representation (our usual numbers like 4, 5, 10, 311, etc) negative and positive numbers cancel each other out. Adding 6 and -6 would result in 0. This property should not be lost in binary as well. So, if we add 6 and -6 in binary, we should get 0.
Imagine we have 4 bits to represent a number and a single bit to store the sign. So, there are 5 bits in total. So, 6 will be represented as
00110, while 0 will be represented as 00000. The binary representation of -6 should be the opposite of 6 so that the sum results in 0. Jumping a bit ahead, the representation of -6 would be 11010. Therefore, if we add 00110 and 11010 in binary, it will result in 00000.To switch from positive to negative and back in binary, we can use a simple trick of flipping all the bits (all the 0s to 1s and all the 1s to 0s) and then adding 1 to the resulting number.
x = 6 # 00110
x = ~x + 1 # Flip all the bits and add 1 => -6
x = ~x + 1 # Flip all the bits and add 1 => 6
z = 0 # 00000
z = ~z + 1 # Flip and +1 => 0
z = ~z + 1 # Flip and +1 => 0
z = ~z # -1 (all 1s in the binary representation)
z = ~z # 0 (all 0s in the binary representation)Note that adding a number in binary is the same as you’d add a number in decimal from the least significant digit to the most significant (along with keeping the carry number).
Depending on the language and implementation, computers store the numbers differently. Languages like C++ and Java have different types for different ranges of numbers. The type
int stores integers in 32 bits: 31 bits for the number and the front bit for the sign ⇒ the numbers can range from -2,147,483,648 () to 2,147,483,647 (). Note that the positives are less than one. This is due to the fact that positives start with a 0-bit and the first number that starts with a 0-bit is 0 itself (all 0s).Challenge
In the magical land of 7s, everything is aligned to have something related to the number 7. So, in this land computer scientists have developed a system where they store their binary numbers in 77 bits (both positive and negative).
Given a bit-string
b, you are asked to calculate the negative value of that number and represent it in 77 bits.Input
The input contains a single line representing the bit-string
b (1 ≤ |b| ≤ 77). It can represent both a positive and a negative number.Output
The output should contain a single line representing
-b with length 77.Examples
Input | Output |
1 | 11111111111111111111111111111111111111111111111111111111111111111111111111111 |
11111111111111111111111111111111111111111111111111111111111111111111111111111 | 00000000000000000000000000000000000000000000000000000000000000000000000000001 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB