Binary to Decimal

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

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

Q: Можешь ли ты преобразовать двоичное число в десятичное с помощью битовых сдвигов?

Да. value << 1 удваивает значение, а | digit устанавливает младший бит, поэтому value = (value << 1) | digit делает то же самое, что и value * 2 + digit . Форма со сдвигом ясно показывает, что вы перемещаете биты, а арифметическая форма также работает для оснований, отличных от 2.

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

+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.

+16 скрытых тестов при отправке

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

Можешь ли ты прочитать число, записанное в системе счисления с основанием от 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, и результат нужно преобразовать обратно в целое число.

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

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

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

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

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

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

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

Можешь ли ты преобразовать двоичное число в десятичное с помощью битовых сдвигов?

Да. value << 1 удваивает значение, а | digit устанавливает младший бит, поэтому value = (value << 1) | digit делает то же самое, что и value * 2 + digit. Форма со сдвигом ясно показывает, что вы перемещаете биты, а арифметическая форма также работает для оснований, отличных от 2.

Python

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

Тестовые случаи

Случай 1

Случай 2

Случай 3

Ввод

s = "1101"

Ожидается