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.

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

Yes. value = (value << 1) | digit does the same as value * 2 + digit : the shift doubles the value and the or sets the lowest bit. 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.

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, set by how far it sits from the right end. You can add those powers from the right, or read from the left and double the value at every step: the same loop that reads decimal text, with 2 in place of 10.

Add place values from the right

Intuition

The rightmost digit is worth 1, and each place to the left is worth twice the one before it. 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 at every 1.

Every digit is visited once: O(n) time and two numbers of memory.

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

Keep value, the number spelled by the digits read so far. Appending one more digit shifts every earlier digit one place left, which doubles its worth, and then adds the new digit: value = value * 2 + digit. For 1101, value goes 1, 3, 6, 13.

Each prefix of the string is a smaller binary number and the loop holds exactly that number, so after the last digit it holds the answer. The value never exceeds the final answer, so a 32-bit integer is enough for 31 digits. No power is ever computed.

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

Giving the leftmost digit the place value 1. 1101 then reads as 11.
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.
Doubling power after the last digit in a 32-bit integer. For a 31-digit string it reaches 2^31, which wraps around or crashes; keep it in 64 bits or skip the last doubling.

Frequently asked questions3

How do you convert binary to decimal?

Give each digit a place value, a power of two that starts at 1 on the right end, and add the place values of the digits that are 1. Or read the digits from the left and set value = value * 2 + digit at each step.

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.

Can you convert binary to decimal with bit shifts?

Yes. value = (value << 1) | digit does the same as value * 2 + digit: the shift doubles the value and the or sets the lowest bit. The arithmetic form also works for bases other than 2.