fb pixel

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

  • Integer to binary

    There are several observations we can make about the binary representation of the number:
    1. The last bit represents if the number is divisible by 2 or not. If it’s 1 ⇒ the number is odd, if it’s 0 ⇒ the number is even. This happens because we add powers of 2 which are even numbers all the way except the last bit. The sum of even numbers will always be even, so, the only way to make the number odd is by adding 1 to that even number. And adding 1 is only possible if the last bit of the number is 1.
    1. Dividing the number by 2 is basically “shifting” the binary representation to the right and removing the last bit. In case we do an integer division and discard the remainder, we can think of dividing n by 2 as shifting the binary representation to the right (dividing all the powers of 2 by 2). If n = a + b + c + d, and all a, b, c, and d are powers of 2. Then dividing n by 2, is the same as dividing the sum by 2 ⇒ n/2 = a/2 + b/2 + c/2 + d/2.
    1. Similarly, multiplying a number by 2 is basically “shifting” the binary representation to the left and adding one 0 on the right. We can think of multiplying all the powers of 2 by 2. If n = a + b + c + d, and all a, b, c, and d are powers of 2. Then multiplying n by 2, is the same as multiplying the sum by 2 ⇒ n·2 = a·2 + b·2 + c·2 + d·2.
    These observations are very helpful to form an intuition about binary numbers and what they represent. They appear in the most subtle ways in different problems and have a wide usage when working with binary representations.
     
    Having an integer n (like 311), we can get the value of the last bit in the binary representation by checking if the number is divisible by 2:
    1. 311 is an odd number ⇒ the last bit is going to be 1 (result = 1). Then we can “shift” the binary representation by dividing 311 by 2 and discarding the last bit which we already know was 1.
    1. 311 / 2 = 155 ⇒ 155 is also odd ⇒ the last bit is also 1 (result = 11). We can discard that bit by dividing the number by 2.
    1. 155 / 2 = 77 ⇒ 77 is also odd ⇒ the last bit is also 1 (result = 111). Let’s discard the last bit by dividing 77 by 2.
    1. 77 / 2 = 38 ⇒ 38 is even ⇒ the last bit is 0 this time (result = 0111).
    1. 38 / 2 = 19 ⇒ 19 is even ⇒ the last bit is 1 (result = 10111).
    1. 19 / 2 = 9 ⇒ odd (result = 110111).
    1. 9 / 2 = 4 ⇒ even (result = 0110111).
    1. 4 / 2 = 2 ⇒ even (result = 00110111).
    1. 2 / 2 = 1 ⇒ odd (result = 100110111).
    1. 1 / 2 = 0 ⇒ we stop here.
    So, by “shifting” the binary representation and checking for the number to be odd or even, we got the binary representation.
    Power of 2
    Power of 2 in decimal
    512
    256
    128
    64
    32
    16
    8
    4
    2
    1
    Binary (include/exclude)
    0
    1
    0
    0
    1
    1
    0
    1
    1
    1
    Sum (311)
    311
    311
    55
    55
    55
    23
    7
    7
    3
    1

    Challenge

    Given an integer n, you are asked to find its binary representation.

    Input

    The only line of the input contains a single integer n (1 ≤ n ≤ ).

    Output

    The program should print the binary representation. The first bit should always be 1.

    Examples

    Input
    Output
    311
    100110111
    5
    101
    6
    110
    7
    111
     
     
    To check your solution you need to sign in
    Sign in to continue