Какой алгоритм можно использовать для преобразования десятичных чисел, введенных в компьютер
Обновлено: 03.07.2024
Предположим, я даю вам это двоичное число 11111110, которое хранится в виде дополнения до двух на машине, и я хочу, чтобы вы нашли его десятичный эквивалент. Некоторые могут сказать, что это -2, а некоторые могут сказать, что это 254, поскольку они не знают, подписано оно или нет. (Я знаю, что это число со знаком, поэтому я взял его дополнение и добавил 1, что дало мне 2, поэтому ответ равен -2. Но если бы я не знал знака, я бы сказал 254).
Короче говоря, как компьютер без ошибок преобразует такое двоичное представление, хранящееся в дополнении до 2, в его десятичный эквивалент?
Знает ли компьютер о своем знаке? (если да, то где хранится эта информация?)
2 ответа 2
Технически вы не можете преобразовать двоичное представление числа в десятичное, потому что компьютеры не имеют никакого хранилища для представления десятичных чисел.
На практике это может показаться абсурдным, поскольку мы всегда имеем дело с числами в десятичном представлении. Но эти десятичные представления никогда не хранятся в десятичном формате. Единственное, что делает компьютер, — это преобразует число в десятичное представление при его отображении. И это преобразование связано с созданием программ и проектированием библиотек.
Приведу небольшой пример на языке C. В C у вас есть знаковые и беззнаковые целые переменные. Когда вы пишете программу, эти переменные используются для хранения чисел в памяти. Кто знает их знаки? Компилятор. Языки ассемблера имеют знаковые и беззнаковые операции. Компилятор отслеживает знак всех переменных и генерирует соответствующий код для знакового и беззнакового случая. Таким образом, ваша программа отлично работает с целыми числами со знаком или без знака, когда она скомпилирована.
Предположим, вы использовали предложение printf для вывода целочисленной переменной и использовали преобразователь формата %d для вывода значения в десятичном представлении. Это преобразование будет выполняться функцией printf, определенной в стандартной библиотеке ввода-вывода C. Функция считывает переменную из памяти, преобразует двоичное представление в десятичное представление, используя простой базовый алгоритм преобразования. Но целью алгоритма является последовательность символов, а не целое число. Таким образом, этот алгоритм делает две вещи: он преобразует двоичное представление в десятичное; и он преобразует биты в значения символов (или, если быть более точным, в коды ASCII). printf должен знать знак числа для успешного выполнения преобразования, и эта информация снова предоставляется конструкциями компилятора, размещенными во время компиляции. Используя эти конструкции, printf может проверить, является ли целое число знаковым или беззнаковым, и использовать соответствующий метод преобразования.
Другие языки программирования идут по тому же пути. По сути, числа всегда хранятся в двоичном виде. Представление со знаком или без знака известно компилятору/интерпретатору и, следовательно, является общеизвестным. Десятичное преобразование выполняется только из косметических соображений, и целью преобразования является последовательность символов или строка.
Изучая информатику, вы, вероятно, так или иначе познакомились с идеей двоичного числа. Двоичное представление важно в информатике, поскольку все значения, хранящиеся в компьютере, существуют в виде строки двоичных цифр, строки нулей и единиц. Без возможности преобразования между обычными представлениями и двоичными числами нам пришлось бы очень неудобно взаимодействовать с компьютерами.
Целые значения являются общими элементами данных. Они постоянно используются в компьютерных программах и вычислениях. Мы узнаем о них на уроках математики и, конечно же, представляем их с помощью десятичной системы счисления или основания 10. Десятичное число \(233_\) и его соответствующий двоичный эквивалент \(11101001_\) интерпретируются соответственно как
\(2\times10^ + 3\times10^ + 3\times10^\)
\(1\times2^ + 1\times2^ + 1\times2^ + 0\times2^ + 1\times2^ + 0\times2^ + 0\times2^ + 1\times2^\)
Но как мы можем легко преобразовать целые значения в двоичные числа? Ответом является алгоритм под названием «Разделение на 2», который использует стек для отслеживания цифр двоичного результата.
Алгоритм деления на 2 предполагает, что мы начинаем с целого числа больше 0. Затем простая итерация непрерывно делит десятичное число на 2 и отслеживает остаток. Первое деление на 2 дает информацию о том, является ли значение четным или нечетным. Четное значение будет иметь остаток 0. Оно будет иметь цифру 0 в разряде единиц. Нечетное значение будет иметь остаток 1 и будет иметь цифру 1 на месте единиц. Мы думаем о построении нашего двоичного числа как о последовательности цифр; первый остаток, который мы вычисляем, на самом деле будет последней цифрой в последовательности. Как показано на рис. 5, мы снова видим свойство реверсирования, которое сигнализирует о том, что стек, вероятно, является подходящей структурой данных для решения проблемы.
Рисунок 5. Преобразование десятичной системы в двоичную ¶
Код Python в ActiveCode 1 реализует алгоритм "Разделить на 2". Функция DivisionBy2 принимает в качестве аргумента десятичное число и многократно делит его на 2. В строке 7 используется встроенный оператор по модулю % для извлечения остатка, а в строке 8 он помещается в стек. После того, как процесс деления достигает 0, в строках 11-13 создается двоичная строка. Строка 11 создает пустую строку. Двоичные цифры извлекаются из стека по одной и добавляются к правому концу строки. Затем возвращается двоичная строка.
Алгоритм двоичного преобразования можно легко расширить для выполнения преобразования для любого основания. В информатике принято использовать несколько различных кодировок. Наиболее распространенными из них являются двоичные, восьмеричные (по основанию 8) и шестнадцатеричные (по основанию 16).
Десятичное число \(233\) и его соответствующие восьмеричные и шестнадцатеричные эквиваленты \(351_\) и \(E9_\) интерпретируются как
\(3\times8^ + 5\times8^ + 1\times8^\)
Функция "divideBy2" может быть изменена таким образом, чтобы она принимала не только десятичное значение, но и основание для предполагаемого преобразования. Идея «разделить на 2» просто заменена более общей «разделить по основанию». Новая функция baseConverter, показанная в ActiveCode 2, принимает десятичное число и любое основание от 2 до 16 в качестве параметров. Остатки по-прежнему помещаются в стек до тех пор, пока преобразуемое значение не станет равным 0. Можно использовать тот же метод построения строки слева направо с одним небольшим изменением. Для чисел с основанием от 2 до 10 требуется максимум 10 цифр, поэтому обычные цифровые символы 0, 1, 2, 3, 4, 5, 6, 7, 8 и 9 работают нормально. Проблема возникает, когда мы выходим за пределы базы 10. Мы больше не можем просто использовать остатки, так как они сами представлены двузначными десятичными числами. Вместо этого нам нужно создать набор цифр, которые можно использовать для представления остатков после 9.
Решение этой проблемы состоит в том, чтобы расширить набор цифр, включив в него некоторые символы алфавита. Например, шестнадцатеричный использует десять десятичных цифр вместе с первыми шестью символами алфавита для 16 цифр. Для реализации этого создается строка цифр (строка 4 в листинге 6), в которой цифры хранятся в соответствующих позициях. 0 находится в позиции 0, 1 — в позиции 1, A — в позиции 10, B — в позиции 11 и так далее. Когда остаток удаляется из стека, его можно использовать для индексации строки цифр, и правильная полученная цифра может быть добавлена к ответу. Например, если из стека удалить остаток 13, к результирующей строке будет добавлена цифра D.
Я новичок в программировании. Просто прочитайте несколько статей об алгоритме преобразования десятичного числа или строки в двоичное число. Но, насколько мне известно, компьютеры хранят эти данные в бинарной форме. Так почему бы нам просто не прочитать необработанный двоичный файл в памяти? Разве это не намного проще и быстрее? Если возможно, как это сделать на C или ассемблере?
Мне просто нужна двоичная форма входного числа, например: проверить, является ли положительное число степенью двойки или нет. Моя идея такова: если N=2^k (N и k — положительные целые числа), то двоичная форма N равна 100,0 (k раз 0).
3 ответа 3
Мы работаем с двоичными представлениями чисел внутри компании, но в конечном итоге люди хотят использовать компьютерную программу, а там такой формат непригоден. Поэтому нам нужен код для преобразования строковых представлений вещей в двоичные, но только для новых данных, введенных пользователем.
Люди очень плохо запоминают насыщенные информацией представления. Именно поэтому мы в первую очередь изобрели алфавит. Поэтому, если пользователь вводит цену или возраст, они входят в программу как последовательность символов. Чтобы выполнить с ними какие-либо арифметические действия, компьютер должен преобразовать их в числа, что практически на всех цифровых компьютерах означает создание битового шаблона, соответствующего этому числу.
Гораздо чаще возникает обратная проблема: программа сохранила значение в виде числа, но пользователь хотел бы видеть удобочитаемую последовательность цифр. Это означает, что компьютер должен отформатировать число обратно в соответствии с синтаксисом ввода (или запомнить исходное представление).
Это правда, что весь программный бизнес стал бы проще, если бы люди научились понимать двоичные представления, но это невозможно, пока мы не изобретем какой-нибудь серьезный трюк нейропрограммирования, так что пока поскольку мы все время застреваем в преобразовании чисел туда и обратно.
Да, это правда. И строки, и десятичные числа, а также все остальные типы представлены в двоичном формате.
Однако проблема заключается в значимости двоичного файла. Вы не можете просто прочитать строку как десятичное число, или, по крайней мере, вы не должны этого делать, если хотите получить десятичное представление этого десятичного числа.
Возьмите, например, эту строку в ASCII: "1.5"
В двоичном формате это представлено массивом байтов размером 4 или больше.
Если бы это интерпретировалось как двойное, значение было бы:
Какое это имеет отношение к числу 1,5? Они используют одно и то же бинарное сообщение, но поскольку бинарность хороша настолько, насколько хороша его интерпретация, этот двойник не имеет смысла. Эта интерпретация усложняется еще больше, если учесть, что некоторые системы предпочитают сохранять десятичную информацию в формате с обратным порядком байтов или прямым порядком байтов, а это означает, что вы также зависите от системы, с которой работаете.
Чтобы преобразовать это в двойное, вам нужно будет разобрать этот двоичный файл, как это было задумано. Как оказалось, эквивалентное преобразование 1,5 в шестнадцатеричное число равно 0x3FF8000000000000.
Если вы предпочитаете точность, то, как правило, вы склонны сохранять в своей программе только строковую форму. Точно так же, если вам нужно использовать это значение в вычислениях, вы сохраняете форму с плавающей запятой или двойную форму. Итак, что произойдет, если вам нужны оба? Вы сохраняете оба в своей программе, используя ту форму, которая лучше всего подходит для точности или расчета. Давно прошли те дни, когда хранение обоих в памяти могло быть проблемой (за исключением нескольких исключений, когда скорость была критична, например, в случае с драйверами).
Если вы хотите определить, является ли строковое представление числа степенью двойки, вычисления для этого будут более сложными, чем простое преобразование его сначала в число. Как только это число, определение того, является ли оно степенью двойки, является тривиальным, поскольку любая двоичная строка содержит ровно одну единицу (в случае десятичного числа вы также должны проверять двоичные строки, содержащие ровно один 0 для отрицательных десятичных значений) .
Читайте также: