Binary to Decimal

Q: Какова временная сложность преобразования двоичного числа в десятичное?

Оба цикла проходят по каждому из n символов один раз, поэтому работают за время O(n) . Они хранят только одно или два числа, что требует O(1) дополнительной памяти. Для строки из 31 символа это 31 шаг.

НовичокМатематика и моделирование Битовые операции

+10

Тебе дана строка s, в которой неотрицательное число записано в двоичной системе счисления с использованием только символов 0 и 1. Верни значение этого числа в виде обычного целого числа. В строке нет ведущих нулей, кроме числа ноль, которое представлено единственным символом 0.

Функция

toDecimal(s: string) → integer

sstring: двоичные цифры числа
Возвращаетinteger: значение s как целое число

Ограничения

1 ≤ s.length ≤ 31
s содержит только 0 и 1.
s начинается с 1, если только s не равно "0".
Считывай цифры самостоятельно, а не вызывай встроенную функцию преобразования основания системы счисления.

Примеры

Ввод: s = "1101"
Вывод: 13
Пояснение: Если считать справа налево, разряды имеют значения 1, 2, 4 и 8. В числе 1101 единицы стоят в разрядах со значениями 8, 4 и 1, а 8 + 4 + 1 = 13.

Ввод: s = "0"
Вывод: 0
Пояснение: У отдельного 0 нет 1 ни в одном разряде, поэтому его значение равно 0.

Ввод: s = "10000000"
Вывод: 128
Пояснение: У единственной 1 справа семь 0, поэтому она находится на месте, соответствующем 2^7 = 128.

Дополнительный вопрос

Можешь ли ты прочитать число, записанное в системе счисления с основанием от 2 до 16, с помощью того же цикла, где буквы a–f обозначают цифры от 10 до 15?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Каждая двоичная цифра обозначает степень двойки, определяемую тем, насколько далеко она находится от правого края. Можно складывать эти степени, начиная справа, или читать строку слева и удваивать значение на каждом шаге. Цикл удвоения никогда не вычисляет степень и является тем же циклом, который используется для чтения десятичного текста, только вместо 10 в нём используется 2.

Складывайте разряды справа

Идея

Самая правая цифра имеет значение 1, следующая — 2, затем 4, 8 и так далее, удваиваясь с каждым шагом влево. Число — это сумма разрядных значений, соответствующих цифрам 1. Поэтому проходи от последнего символа к первому, храни текущее разрядное значение в power и добавляй его, если цифра равна 1.

Для 1101 ты встречаешь 1 (прибавь 1), 0 (пропусти 2), 1 (прибавь 4) и 1 (прибавь 8); в сумме получается 13. Каждая цифра посещается один раз, поэтому цикл выполняется за время O(n) и использует память для двух чисел.

Следи за размером power. Для строки из 31 цифры на последней цифре значение достигает 2^30, после чего удваивается ещё раз до 2^31, что не помещается в знаковое 32-битное целое число. Храни power в 64-битной переменной или прекращай удвоение после последней цифры.

Алгоритм

Задайте 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, затем 1 * 2 + 1 = 3, затем 3 * 2 + 0 = 6, затем 6 * 2 + 1 = 13. Каждый префикс строки — это меньшее двоичное число, и цикл хранит именно это число, поэтому после последней цифры в нём будет всё значение.

Значение никогда не превышает окончательный результат, поэтому для строки из 31 цифры оно остаётся в пределах 2^31-1, и 32-битного целого числа достаточно. Цифра — это код символа за вычетом кода '0', что превращает '1' в 1, а '0' — в 0. Это стандартный способ преобразовать текст в число в любой системе счисления.

Алгоритм

Установи 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. Значения разрядов начинаются с правого края, поэтому выполняй обход от последнего символа или используй цикл удвоения слева направо.
Прибавление символа вместо цифры. Во многих языках '1' — это число 49, поэтому value * 2 + '1' даёт слишком большое значение. Сначала вычти '0'.
Переполнение значения разряда. Удвоение power после 31-й цифры даёт 2^31, что приводит к переполнению или сбою в 32-битном целом числе.
Вычисление значения каждого разряда с помощью функции возведения в степень с плавающей точкой. В C, C++ и Java pow(2, k) возвращает double, и результат нужно преобразовать обратно в целое число.

Частые вопросы3

Как преобразовать двоичное число в десятичное?

Назначь каждой цифре разрядное значение: 1 для самой правой, затем 2, 4, 8 и так далее влево. Сложи разрядные значения цифр, равных 1. Для 1101 это 8 + 4 + 1 = 13.

Почему удвоение значения работает?

Если дописать ещё одну цифру в конец двоичного числа, каждая предыдущая цифра сдвинется на один разряд влево, а цена каждого разряда вдвое больше цены разряда справа от него. Поэтому прежнее значение удваивается, а новая цифра добавляет 0 или 1. Повторяя это от первой цифры до последней, можно получить всё число.

Какова временная сложность преобразования двоичного числа в десятичное?

Оба цикла проходят по каждому из n символов один раз, поэтому работают за время O(n). Они хранят только одно или два числа, что требует O(1) дополнительной памяти. Для строки из 31 символа это 31 шаг.

def toDecimal(s):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргумент

s = "1101"

Ожидаемый вывод