Binary Representation of Numbers
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).Output
The program should print the actual number.
Examples
Input | Output |
0100110111 | 311 |
101 | 5 |
110 | 6 |
111 | 7 |
Constraints
Time limit: 1 seconds
Memory limit: 512 MB
Output limit: 1 MB