Блог

Возьмем, к примеру, строку s="556852144786" , представляющую десятичное число n=556852144786 . Существует ли прямой алгоритм для ее преобразования в s1="1000000110100110..." 1000000110100110... двоичное представление where n ?

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

Для этого существуют различные способы. Вот два, хотя, если вы прищуритесь достаточно сильно, они представляют собой почти один и тот же алгоритм.

Метод 1. повторно разделите десятичную строку на два

В этом методе мы повторно делим исходную десятичную строку на 2 (используя десятичную арифметику) и отслеживаем остатки: эти остатки дают вам биты результата в обратном порядке. Вот как выглядит этот алгоритм в Python. В нем отсутствуют определения is_nonzero и divide_by_two . Мы предоставим их позже.

 def dec_to_bin(s):
    """
    Convert decimal string s to binary, using only string operations.
    """
    bits = ""
    while is_nonzero(s):
        s, bit = divide_by_two(s)
        bits  = bit
    # The above builds up the binary string in reverse.
    return bits[::-1]
  

Алгоритм генерирует биты в обратном порядке, поэтому нам нужен окончательный реверс, чтобы получить результирующую двоичную строку.

divide_by_two Функция принимает десятичную строку s и возвращает новую десятичную строку, представляющую частное s / 2 вместе с остатком. Остаток представляет собой один бит, снова представленный в виде строки — или "0" или "1" . Это следует обычному методу деления слева направо, которому учат в школе: каждый шаг включает в себя деление одной цифры вместе с переносом, полученным из предыдущего шага, на два. Вот эта функция:

 def divide_by_two(s):
    """
    Divide the number represented by the decimal string s by 2,
    giving a new decimal string quotient and a remainder bit.
    """
    quotient = ""
    bit = "0"
    for digit in s:
        quotient_digit, bit = divide_digit_by_two(bit, digit)
        quotient  = quotient_digit
    return quotient, bit
  

Нам осталось определить, который принимает одну цифру плюс десятичный бит переноса и делит на два, чтобы получить цифру и остаток в один бит. divide_digit_by_two На этом этапе все входные и выходные данные представляют собой строки длиной один. Здесь мы обманываем и используем целочисленную арифметику, но существует только 20 возможных различных комбинаций входных данных, поэтому вместо этого мы могли бы легко использовать таблицу поиска.

 def divide_digit_by_two(bit, digit):
    """
    Divide a single digit (with tens carry) by two, giving
    a digit quotient and a single bit remainder.
    """
    digit, bit = divmod(int(bit) * 10   int(digit), 2)
    return str(digit), str(bit)
  

Вы можете представить divide_digit_by_two себе примитивную арифметическую операцию, которая меняет местами две цифры в разных базисах: она преобразует неотрицательное целое число, меньшее, чем 20 представлено в форме 10 * bit digit , в то же значение, представленное в форме 2 * digit bit .

Нам все еще не хватает одного определения: определения is_nonzero . Десятичная строка представляет ноль тогда и только тогда, когда она полностью состоит из нулей. Вот быстрый тест на Python для этого.

 def is_nonzero(s):
    """
    Determine whether the decimal string s represents zero or not.
    """
    return s.strip('0') != ''
  

И теперь, когда у нас есть все биты на месте, мы можем протестировать:

 >>> dec_to_bin("18")
'10010'
>>> dec_to_bin("556852144786")
'1000000110100110111110010110101010010010'
>>> format(556852144786, 'b')  # For comparison
'1000000110100110111110010110101010010010'
  

Способ 2. многократно умножьте двоичную строку на 10

Вот вариант первого метода: вместо повторяющихся делений мы обрабатываем входящую десятичную строку цифра за цифрой (слева направо). Мы начинаем с пустой двоичной строки, представляющей значение 0 , и каждый раз, когда мы обрабатываем цифру, мы умножаем на 10 (в двоичном представлении) и добавляем значение, представленное этой цифрой. Как и раньше, удобнее всего создавать двоичную строку в порядке младшего конца (сначала младший значащий бит), а затем в обратном порядке в конце, чтобы получить традиционное представление в формате big-endian. Вот функция верхнего уровня:

 def dec_to_bin2(s):
    """
    Convert decimal string s to binary, using only string operations.

    Digit-by-digit variant.
    """
    bits = ""
    for digit in s:
        bits = times_10_plus(bits, digit)
    return bits[::-1]
  

Задача times_10_plus функции состоит в том, чтобы взять двоичную строку и цифру и создать новую двоичную строку, представляющую результат умножения значения оригинала на десять и добавления значения двоичной цифры. Это выглядит так:

 def times_10_plus(bits, digit):
    """
    Multiply the value represented by a binary string by 10, add a digit,
    and return the result as a binary string.
    """
    result_bits = ""
    for bit in bits:
        digit, result_bit = divide_digit_by_two(bit, digit)
        result_bits  = result_bit
    while digit != "0":
        digit, result_bit = divide_digit_by_two("0", digit)
        result_bits  = result_bit
    return result_bits
  

Обратите внимание, что мы используем точно такой же арифметический примитив divide_digit_by_two , как и раньше, но теперь мы думаем о нем немного по-другому: он умножает один бит на десять, добавляет переносную цифру и превращает ее в новый бит (младший значащий бит результата) вместе с новой переносной цифрой.

Примечания по эффективности

В интересах ясности я оставил некоторые недостатки на уровне Python. В частности, при создании строк было бы более эффективно создать список битов или цифр, а затем выполнить конкатенацию с str.join помощью операции в самом конце. Также обратите внимание, что в зависимости от языка реализации может иметь смысл изменять либо строку цифр, либо строку битов на месте, вместо того, чтобы генерировать новую строку на каждом шаге. Я оставляю необходимые изменения на ваше усмотрение.