Decimal to Binary

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

Да. n & 1 даёт младший бит, а n >> 1 удаляет его, что для неотрицательных чисел равносильно n % 2 и n / 2 . Цикл и обращение остаются такими же. Деление проще объяснить, тогда как вариант со сдвигом часто используется в низкоуровневом коде.

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

+10

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

Функция

toBinary(n: integer) → string

ninteger: число для преобразования
Возвращаетstring: двоичные цифры n в виде строки

Ограничения

0 ≤ n ≤ 2³¹-1
Создайте строку самостоятельно, вместо того чтобы вызывать встроенную функцию преобразования системы счисления.

Примеры

Ввод: n = 13
Вывод: "1101"
Пояснение: 13 = 8 + 4 + 1. В разрядах для 8, 4, 2 и 1 стоят 1, 1, 0 и 1, что читается как 1101.

Ввод: n = 0
Вывод: "0"
Пояснение: У нуля нет установленных битов, но в ответе всё равно должна быть одна цифра, поэтому это "0", а не пустая строка.

Ввод: n = 64
Вывод: "1000000"
Пояснение: 64 — это 2^6, одна 1 в разряде 64, за которой следуют шесть 0 для разрядов от 32 до 1.

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

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

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

Подсказки

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

Открыто 0 из 3

Решение

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

Вычитайте степени двойки сверху

Идея

Вот как выполнить преобразование вручную. Найдите наибольшую степень двойки, которая не превышает n; это первая цифра — 1. Затем переходите вниз по одной степени за раз. Если степень всё ещё не превышает оставшееся число, запишите 1 и вычтите её; в противном случае запишите 0.

Для 13 наибольшая степень — 8. Запишите 1, и останется 5. Затем подходит 4 (1, остаётся 1), 2 не подходит (0), а 1 подходит (1). Получаются цифры 1101. Первая цифра всегда равна 1, поэтому ведущий ноль появиться не может.

При поиске наибольшей степени нужна осторожность. Удвоение power до тех пор, пока оно не превысит n, приводит к переполнению 32-битного целого числа, когда n ≥ 2^30, поскольку следующая степень равна 2^31. Удваивая число только пока power ≤ n / 2, вы остановитесь на нужной степени, ни разу не превысив n. Для 31-битного числа потребуется 31 шаг, что составляет O(log n).

Алгоритм

Если n равно 0, верните "0".
Установите power равным 1 и удваивайте его, пока power ≤ n / 2.
Пока power > 0: если n ≥ power, добавьте 1 и вычтите power из n; иначе добавьте 0.
Разделите power пополам и повторите.
Верните добавленные цифры.

def toBinary(n):
    if n == 0:
        return "0"
    # Largest power of two that is at most n. Comparing with n // 2 avoids overflow.
    power = 1
    while power <= n // 2:
        power *= 2
    bits = []
    while power > 0:
        if n >= power:
            bits.append("1")
            n -= power
        else:
            bits.append("0")
        power //= 2
    return "".join(bits)

Повторное деление на 2

Идея

Последняя двоичная цифра числа n показывает, является ли n нечётным: это n % 2. Деление на 2 с отбрасыванием остатка сдвигает каждую цифру на одну позицию вправо, поэтому следующей последней цифрой становится предыдущая. Повторяй, пока ничего не останется, и собирай все цифры, начиная с младшей.

Для 13: при делении 13 остаток равен 1, 6 — 0, 3 — 1, а 1 — 1, после чего число становится равным 0. Остатки по порядку: 1, 0, 1, 1; в обратном порядке они дают 1101. Цикл останавливается, когда число достигает 0, поэтому записываемая им старшая цифра всегда равна 1 и ведущий ноль не появляется. Само число 0 никогда не попадает в цикл, поэтому для него нужна отдельная проверка.

На каждом шаге число уменьшается вдвое, поэтому для 31-битного значения требуется 31 шаг, время работы составляет O(log n), а строка цифр занимает O(log n) памяти.

Алгоритм

Если n равно 0, верните "0".
Пока n > 0, добавляйте n % 2 как цифру и присваивайте n значение n / 2, округлённое вниз.
Переверните цифры, потому что они получились в обратном порядке.
Верните их в виде строки.

def toBinary(n):
    if n == 0:
        return "0"
    bits = []
    while n > 0:
        # The remainder is the lowest bit that is left.
        bits.append(str(n % 2))
        n //= 2
    # The bits came out lowest first, so turn them around.
    bits.reverse()
    return "".join(bits)

Ловушки и крайние случаи

Цикл короткий, и большинство неправильных ответов связано с его двумя крайними случаями.

Возврат пустой строки для 0. Для нуля цикл деления не выполняется, поэтому сначала проверьте его.
Забыть выполнить разворот. Остатки появляются начиная с младшей цифры, поэтому вместо 110 получается 011.
Использовать / в языке, где он возвращает дробное число, например в JavaScript, Lua или PHP. 13 / 2 должно дать 6, поэтому округляйте вниз или используйте целочисленное деление.
Увеличивать наибольшую степень двойки вдвое, пока она не превысит n. Для n = 2^31-1 следующая степень, 2^31, не помещается в 32-битное целое число.
Выделить слишком мало памяти в C. Для 31-битного числа нужны 31 символ и завершающий '\0'.

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

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

Снова и снова дели число на 2, записывая каждый остаток, пока число не достигнет 0. Прочитай остатки от последнего к первому. Для 13 остатки равны 1, 0, 1, 1, поэтому 13 в двоичной системе — это 1101.

Почему остатки считываются в обратном порядке?

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

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

На каждом шаге число уменьшается вдвое, поэтому цикл выполняется один раз для каждой двоичной цифры, то есть примерно log2(n) раз. Это время O(log n), а строка ответа занимает O(log n) памяти. Для 32-битного целого числа это не более 31 шага.

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

Да. n & 1 даёт младший бит, а n >> 1 удаляет его, что для неотрицательных чисел равносильно n % 2 и n / 2. Цикл и обращение остаются такими же. Деление проще объяснить, тогда как вариант со сдвигом часто используется в низкоуровневом коде.

Python

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

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

Случай 1

Случай 2

Случай 3

Ввод

n = 13

Ожидается

"1101"