Binary to Decimal
你会得到一个字符串 s，它用二进制表示一个非负数，只包含字符 0 和 1。请以普通整数的形式返回这个数的值。除数字零由单个字符 0 表示外，字符串没有前导零。
函数
- sstring
- 这个数字的二进制位
- 返回值integer
- s 的整数值
约束条件
1 ≤ s.length ≤ 31s只包含0和1。s以1开头，除非s是"0"。- 自己读取这些数字，而不是调用内置的进制转换功能。
示例
- 输入
- s = "1101"
- 输出
- 13
- 解释
- 从右边开始，各位的值分别是 1、2、4 和 8。
1101在值为 8、4 和 1 的位上都是 1，因此8 + 4 + 1 = 13。
- 输入
- s = "0"
- 输出
- 0
- 解释
- 单个
0在任何数位上都没有 1，所以它的值是0。
- 输入
- s = "10000000"
- 输出
- 128
- 解释
- 唯一的 1 右边有 7 个 0，所以它位于表示
2^7 = 128的数位上。
进阶
你能用同一个循环读取一个以 2 到 16 进制表示的数字吗？其中字母 a 到 f 分别代表数字 10 到 15。
提示
逐个打开提示，每个都会多透露一点。
在十进制中，
347中的各位数字分别表示 300、40 和 7。二进制中的每一位数字表示多少？最右边的二进制位表示 1，每向左移动一位，位值就加倍：1、2、4、8，依此类推。这个数等于所有值为 1 的位值之和。
你可以不用计算幂：从左向右读取，每读到一位数字，就把当前值乘以 2，再加上这一位数字。读完最后一位后，当前值就是答案。
题解
每个二进制位都代表一个 2 的幂，具体取决于它距离右端有多远。你可以从右边开始把这些幂相加，也可以从左边开始读取，并在每一步将值翻倍：这和读取十进制文本的循环相同，只是把 10 换成 2。
从右侧开始相加位值
思路
最右边的数字代表 1，左边每一位的位值都是前一位的两倍。这个数等于所有值为 1 的位值之和，因此从最后一个字符向前遍历，将当前位值保存在 power 中，并在遇到每个 1 时将它加上。
每个数字只访问一次：时间复杂度为 O(n)，使用两个数字的内存。
算法
- 将
total = 0和power = 1设好。 - 从字符串的最后一个字符开始，向前遍历到第一个字符。
- 如果字符是
1，就将power加到total上。 - 向左移动一位之前，将
power加倍。 - 返回
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从左侧开始翻倍并相加
思路
让 value 保存目前读到的数字所表示的数。每追加一位数字，之前的每一位都会左移一位，数值翻倍，然后再加上新的一位：value = value * 2 + digit。对于 1101，value 依次变为 1、3、6、13。
字符串的每个前缀都是一个更小的二进制数，而循环中始终保存的正是这个数，所以读完最后一位后，它保存的就是答案。这个值不会超过最终答案，因此 31 位数字用 32 位整数就够了。整个过程不会计算幂。
算法
- 将
value = 0。 - 从左到右处理每个字符，将它减去
'0'的编码，转换成数字。 - 设置
value = value * 2 + digit。 - 返回
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
易错点和边界情况
- 把最左边的数字的位值设为 1。这样，
1101就表示 11。 - 把字符加进去，而不是把数字加进去。在许多语言中，
'1'表示数字 49，所以value * 2 + '1'会大得多；应先减去'0'。 - 在 32 位整数中，处理完最后一位数字后再将
power加倍。对于长度为 31 位的字符串，它会达到2^31，导致溢出或崩溃；应将它保存在 64 位整数中，或者跳过最后一次加倍。
常见问题3
如何将二进制转换为十进制？
给每个数字分配一个位值，也就是从最右边的 1 开始的 2 的幂，然后把值为 1 的数字对应的位值相加。或者从左向右读取数字，每一步都设置 value = value * 2 + digit。
将二进制转换为十进制的时间复杂度是多少？
两个循环都会遍历每个 n 个字符一次，因此时间复杂度为 O(n)。它们只保存一个或两个数字，因此额外空间复杂度为 O(1)。
你能用位移把二进制数转换为十进制数吗？
是的。value = (value << 1) | digit 和 value * 2 + digit 的作用相同：移位会将值加倍，按位或会设置最低位。对于 2 进制以外的进制，算术形式也适用。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def toDecimal(s):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
s = "1101"
预期输出
13