We have been working with integers for quite a while. But how are they actually represented in our computers? We know that everything on our machines is either 0 or 1. So, all the integers are represented in some form that is stored as a sequence of 0s and 1s. We call that the binary representation of numbers.
Any number can be represented as a sum of powers of 2 (1, 2, 4, 8, 16, 32, β¦):
19 = 16 + 2 + 1
20 = 16 + 4
140 = 128 + 8 + 4
Therefore, we can create a sequence of 0s and 1s that would represent the powers of 2, and to get the final number, we would just add those up together. In case the representation contains 1 - we include the corresponding power of 2, and in case itβs a 0 - we exclude it. For 140 we included the 128, 8, and 4 powers of 2 while excluding 64, 32, 16, 2, and 1. We can do that for any number:
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
The convention is to write the small powers of 2 on the right, and progress to larger ones as we move to the left. So, we first start from 1, then process 2, then 4, etc.
Starting from the rightmost power of 2 we sum up all the powers of 2 that have a 1 in the binary representation and obtain the final number.
Challenge
Given a binary representation, you are asked to write a program to print the original number.
Input
The only line of the input contains the string s of 0s and 1s (1 β€ |s| β€ 31).