Algorithms and Data Structures

  • Profound Academy

    • Status
      • 1
        Implementation
      • 2
        Bitwise operations
      • 3
        Prefix Sums
      • 4
        Sliding window / Two pointers
      • 5
        Modular Arithmetic
      • 6
        Number Theory
      • 7
        Binary Search
      • 8
        Basic Sorting
      • 9
        Greedy Algorithms
      • 10
        Basic Dynamic Programming
      • 11
        Recursion
      • 12
        Linked LIst
      • 13
        Queue & Stack
      • 14
        Binary tree + BST
      • 15
        Divide & Conquer + Advanced Sorting
      • 16
        Heap
      • 17
        Hashing
      • 18
        Graph Representation
      • 19
        BFS

  • 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: 1 seconds

    Memory limit: 512 MB

    Output limit: 1 MB

    To check your solution you need to sign in
    Sign in to continue