Binary to Decimal

Q: What is the time complexity of converting binary to decimal?

Both loops visit each of the n characters once, so they take O(n) time. They keep only one or two numbers, which is O(1) extra space. For a 31-character string that is 31 steps.

Q: Can you convert binary to decimal with bit shifts?

Yes. value << 1 doubles the value and | digit sets the lowest bit, so value = (value << 1) | digit does the same as value * 2 + digit . The shift form makes it clear that you are moving bits, while the arithmetic form also works for bases other than 2.

BeginnerMath and simulation Bit manipulation

+10

You get a string s that writes a non-negative number in binary, using only the characters 0 and 1. Return the value of that number as an ordinary integer. The string has no leading zeros, except for the number zero, which is the single character 0.

Function

toDecimal(s: string) → integer

sstring: the binary digits of the number
Returnsinteger: the value of s as an integer

Constraints

1 ≤ s.length ≤ 31
s contains only 0 and 1.
s starts with 1, unless s is "0".
Read the digits yourself instead of calling a built-in base conversion.

Examples

Input: s = "1101"
Output: 13
Explanation: Reading from the right, the places are worth 1, 2, 4 and 8. 1101 has 1s in the places for 8, 4 and 1, and 8 + 4 + 1 = 13.

Input: s = "0"
Output: 0
Explanation: A single 0 has no 1 in any place, so its value is 0.

Input: s = "10000000"
Output: 128
Explanation: The only 1 has seven 0s to its right, so it sits in the place worth 2^7 = 128.

+16 hidden tests on Submit

Follow-up

Can you read a number written in any base from 2 to 16 with the same loop, where the letters a to f stand for the digits 10 to 15?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

Each binary digit stands for a power of two, decided by how far it sits from the right end. You can add those powers from the right, or read the string from the left and double the value at every step. The doubling loop never computes a power and is the same loop you use to read decimal text, with 2 in place of 10.

Add place values from the right

Intuition

The rightmost digit is worth 1, the next one 2, then 4, 8 and so on, doubling with every step to the left. The number is the sum of the place values that hold a 1. So walk from the last character to the first, keep the current place value in power, and add it whenever the digit is 1.

For 1101 you meet 1 (add 1), 0 (skip 2), 1 (add 4) and 1 (add 8), which totals 13. Every digit is visited once, so the loop takes O(n) time and two numbers of memory.

Watch the size of power. For a 31-digit string it reaches 2^30 on the last digit and is then doubled once more to 2^31, which does not fit in a signed 32-bit integer. Keep power in a 64-bit variable, or stop doubling after the last digit.

Algorithm

Set total = 0 and power = 1.
Walk the string from its last character to its first.
If the character is 1, add power to total.
Double power before moving one place left.
Return total.

def toDecimal(s):
    total = 0
    power = 1  # the place value of the rightmost digit
    for i in range(len(s) - 1, -1, -1):
        if s[i] == "1":
            total += power
        power *= 2
    return total

Double and add from the left

Intuition

Read the string from the left and keep value, the number spelled by the digits read so far. Appending one more binary digit shifts every earlier digit one place to the left, which doubles their worth, and then adds the new digit. So each step is value = value * 2 + digit.

For 1101, value goes 1, then 1 * 2 + 1 = 3, then 3 * 2 + 0 = 6, then 6 * 2 + 1 = 13. Each prefix of the string is a smaller binary number, and the loop keeps exactly that number, so after the last digit it holds the whole value.

The value never goes above the final answer, so for a 31-digit string it stays within 2^31-1 and a 32-bit integer is enough. The digit is the character code minus the code of '0', which turns '1' into 1 and '0' into 0. This is the standard way to parse a number from text in any base.

Algorithm

Set value = 0.
For each character from left to right, turn it into a digit by subtracting the code of '0'.
Set value = value * 2 + digit.
Return value.

def toDecimal(s):
    value = 0
    for ch in s:
        # Shift the digits read so far one place left, then add the new one.
        value = value * 2 + (ord(ch) - ord("0"))
    return value

Pitfalls and edge cases

Most wrong answers come from the direction of the walk or from the type of the digit.

Giving the leftmost digit the place value 1. The place values start at the right end, so walk from the last character, or use the doubling loop from the left.
Adding the character instead of the digit. In many languages '1' is the number 49, so value * 2 + '1' is far too large. Subtract '0' first.
Overflowing the place value. Doubling power after the 31st digit gives 2^31, which wraps around or crashes in a 32-bit integer.
Computing each place value with a floating point power function. In C, C++ and Java, pow(2, k) returns a double, and the result has to be converted back to an integer.

Frequently asked questions4

How do you convert binary to decimal?

Give each digit a place value: 1 for the rightmost, then 2, 4, 8 and so on toward the left. Add the place values of the digits that are 1. For 1101 that is 8 + 4 + 1 = 13.

Why does doubling the value work?

Writing one more digit at the end of a binary number moves every earlier digit one place left, and each place is worth twice the one to its right. So the old value doubles, and the new digit adds 0 or 1. Repeating this from the first digit to the last builds the whole number.

What is the time complexity of converting binary to decimal?

Both loops visit each of the n characters once, so they take O(n) time. They keep only one or two numbers, which is O(1) extra space. For a 31-character string that is 31 steps.

Can you convert binary to decimal with bit shifts?

Yes. value << 1 doubles the value and | digit sets the lowest bit, so value = (value << 1) | digit does the same as value * 2 + digit. The shift form makes it clear that you are moving bits, while the arithmetic form also works for bases other than 2.