Форум программистов, компьютерный форум, киберфорум
Наши страницы
Evg
Войти
Регистрация
Восстановить пароль
Рейтинг: 5.00. Голосов: 2.

Немного о преобразовании чисел между системами счисления

Запись от Evg размещена 15.02.2012 в 22:21
Обновил(-а) Evg 17.11.2018 в 12:04

ВНИМАНИЕ! Вопросы по существу обсуждаемого вопроса просьба задавать здесь или создать тему на форуме и кинуть на неё ссылку в блог или мне в личку.
Объясняю почему

Причин для этого несколько.

Я, как и любой другой автор, всегда могу упустить интересный момент обсуждаемой темы (что подтвердилось на практике). А потому задаваемый вопрос может закрывать пробел в статье. Ответ на конкретный вопрос, как правило, дать несложно. Сложнее его аккуратно сформулировать так, чтобы ответ являлся законченной частью статьи. Поэтому, как правило, на первых порах я ограничиваюсь конкретным ответом на конкретный вопрос, а в статью временно вставляю ссылку на пост, где был дан ответ. А когда дойдут руки, то вместо ссылки пишу нормальное пояснение. Технические возможности блога не позволяют в комментариях пользоваться широкими возможностями, доступными на форуме (то как выделение текста жирным, вставка фрагментов исходников в удобном для чтения виде и т.п.), поэтому будет удобнее, если вопрос и ответ будут опубликованы на форуме

Любая статья является изложением знаний в общем случае. У многих людей мышление устроено так, что прочтя на форуме конкретный вопрос и конкретный ответ на этот вопрос, у них появится бОльшее понимание, чем после прочтения теоретических выкладок (даже если они подкреплены конкретными примерами). Ссылки на такие обсуждения я, как правило, включаю в последний раздел статьи.

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

Исторически сложилось, что раньше (когда ещё не было блога) статьи располагались на форуме и представлены были в виде двух тем. Первая тема создавалась в специально отведённой свалке и представляла собой черновик, который со временем дорабатывался до законченной статьи. После этого статья переезжала во вторую тему в тематическом разделе. А первая тема оставалась дополнительной свалкой для замечаний и мелких вопросов по теме. Ссылку на старое местоположение данной свалки я помещаю в начале статьи. Вопросы, по возможности, прошу создавать в отдельных темах, но если вопрос действительно мелкий, то можно его задать и в указанной свалке.





1. Пример ошибочного решения

Сразу скажу, что я не собираюсь рассказывать о различных системах счисления и о том как с ними работать. Не собираюсь я и приводить готовых примеров по данной тематике. А хочу я обсудить одну из очень распространённых ошибок, с которой много раз сталкивался на нашем форуме. Эту ошибку допускают не только новички, но и те, кто уже имеет за плечами опыт работы. Судя по тому, что многие приведённые решения удовлетворили спрашивающих, можно сделать вывод, что и преподаватели в этом вопросе разбираются плохо (что в наше время удивительным не является).

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

C
#include <stdio.h>
 
#define SIZE (sizeof(int)*2)
 
char*
DecToHex (int val)
{
  static char buff[SIZE+1];
  static char digits[16] = "0123456789abcdef";
  char *p;
  int i;
 
  p = buff;
  p[SIZE] = '\0';
 
  for (i = 0; i < SIZE; i++)
    p[SIZE - i - 1] = digits[(val >> i*4) & 0xf];
 
  return p;
}
 
int
main (void)
{
  int val;
  char *str;
 
  printf ("Введите десятичное число:\n");
  scanf ("%d", &val);
  str = DecToHex (val);
  printf ("Шестнадцатеричная форма: %s\n", str);
 
  return 0;
}
Данная программа в процессе исполнения действительно делает то, что сказано в условии: мы вводим число в десятичной форме записи, а программа нам печатает это же число, но в шестнадцатеричной форме. И тем не менее данная программа является НЕ правильной. С той точки зрения, что она НЕ удовлетворяет поставленной задаче по своей сути (а не по юридической трактовке).

Прежде, чем объяснить причину, надо будет немного покопаться в теории и детально рассмотреть процесс перевода чисел из различных систем счисления

2. Число и форма записи числа

Строго говоря, понятия типа "десятичное число" НЕ являются корректными. Правильным было бы называть "десятичная форма записи числа". И вот почему. Число - это некий эквивалент некоторой количественной величины. Представим себе, что у нас на столе лежат яблоки. Так вот "число яблок" - это некая мера, которая абстрактно описывает количество яблок в штуках. Числа можно сравнивать, моделируя тем самым физический процесс оценки, на котором из столов больше яблок. Над числами можно проводить операции, например, сложение, моделируя тем самым физический процесс объединение яблок с двух столов. Ну и так далее. Но такое абстрактное понятие как число человеку нужно ещё и как-то воспринимать и уметь передавать при общении. Для этого появилось понятие "запись числа". Т.е. числам придумали названия, придумали некую форму записи на бумажке и т.п. Системы счисления - это всего лишь форма записи (форма представления) чисел. Мы можем сказать, что на столе лежит "31 в десятичном представлении яблок" или "37 в восьмеричном представлении яблок" или "1f в шестнадцатеричном представлении яблок". Мы видим три разные формы записи числа, которые означают одно и то же число, описывающее количество яблок. Другими словами, количество яблок в штуках остаётся одним и тем же независимо от того, в какой системе счисления мы это количество записываем

3. Как мы осуществляем перевод чисел из различных систем счисления

Решим "на бумаге" несложную задачу: имеется восьмеричная запись числа "37". Записать это же число в шестнадцатеричной форме. Решение предельно простое: "37" в восьмеричной форме это 3*8+7=31. Далее 31 эквивалентно 1*16+15, а потому в шестнадцатеричной форме число будет выглядеть как "1f". С виду казалось бы всё просто. Но если посмотреть внимательно на то, что мы сейчас сделали, то увидим, что мы не просто перевели число из восьмеричной формы в шестнадцатеричную. Мы сделали целых два перевода чисел: сначала из восьмеричной формы в десятичную, а потом из десятичной в шестнадцатеричную. Почему мы так сделали? Да потому, что наш мозг привык к десятичной форме записи и мы с лёгкостью можем произвести арифметические операции над десятичными числами в уме или на листочке (не прибегая к калькулятору). Конечно же все эти действия можно было бы выполнять непосредственно производя все операции в восьмеричном представлении, но у 9 человек из 10 в таком случае попросту мозги сломаются, даже для таких небольших чисел. Таким образом для наших мозгов десятичная форма является неким внутренним представлением чисел

4. Так в чём же заключается ошибка

Снова вернёмся к задаче из раздела 1. Чтобы показать принципиальную неправильность решения, сделаем следующее. В вызове scanf заменим "%d" на "%o" и вуаля: наша программа начала переводить числа из восьмеричной формы в шестнадцатеричную. При этом программа содержит в себе функцию DecToHex, которая, судя по названию, должна переводить из десятичной формы в шестнадцатеричную, но, очевидным образом, делает что-то другое. Можно пойти ещё дальше и написать программу таким образом:

C
#include <stdio.h>
 
int
main (void)
{
  int val;
 
  printf ("Введите десятичное число:\n");
  scanf ("%d", &val);
  printf ("Шестнадцатиричная форма: %x\n", val);
 
  return 0;
}
Программа по прежнему выполняет поставленную задачу: мы вводим число в десятичной форме записи, а программа нам пишет это же число, но в шестнадцатеричной форме. Но такую программу не примет даже самый ушлый преподаватель, хотя, как мне кажется, не сможет внятно объяснить, почему пример из раздела 1 он принял бы, а этот пример - нет.

Если мы вспомним то, что делали в разделе 3, то заметим, что в данном случае мы так же осуществляем два перевода числа. Функция scanf выполняет преобразование из строковой десятичной формы записи во внутреннюю форму, с которой работает процессор, и помещает результат в переменную val. Функция printf читает из переменной val число во внутренней форме процессора и переводит его в строковое шестнадцатеричное представление.

Думаю, всем понятно, что в качестве внутренней формы нынешние процессоры используют двоичную. При этом "запись" внутри процессора делается не в виде циферок 0 и 1, а в виде уровней напряжения на транзисторах (низкое или высокое). Конечно, в такие аппаратные дебри вдаваться не стОит, но эти уровни напряжения на абстрактном уровне это и есть те самые пресловутые биты.

Вновь вернёмся к примеру из раздела 1. Теперь можно понять, что автор подобной программы сделал только половину работы: он выполнил преобразование числа из внутренней формы процессора в строковую шестнадцатеричную форму записи. Вторую половину работы выполнила функция scanf (ну или cin для тех, кто пишет на Си++). Если мы посмотрим на прототип функции DecToHex, то увидим, что на вход функция принимает число, а на выходе возвращает запись числа. И, таким образом, название функции DecToHex является некорректным. Понятие "Dec" можно применять лишь к форме записи числа, но не к числу, потому как число - это абстрактная величина, никак не привязанная к системе счисления. Стало быть, функцию DecToHex следовало бы переименовать во что-то типа ValueToHex (или InternalToHex).

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

5. Константы в тексте программы

Ещё некоторое непонимание у людей возникает при работе с константами в тексте программы:

C
int x = 18;
int y = 0x12;
Константа (хотя более правильно называть "литерал") - это такая же запись числа в какой-то из форм счисления. В данном примере мы имеем две константы с одинаковым значением, но разной формой записи. Если мы продизассемблируем полученную программу, то увидем, что в коде программы мы имеем две абсолютно одинаковые кодировки. И причина здесь ровно такая же - в коде программы все константы хранятся во внутреннем машинном представлении (коим можно считать двоичное представление). А переводом из строкового представления во внутреннее в данном случае осуществляет компилятор в момент компиляции программы (compile-time). В отличие от примера из предыдущей главы, где перевод осуществляют функции printf и scanf в момент работы программы (run-time).

6. И всё-таки готовая программа

После общения в личке на данную тему с одним малолетним хамлом у меня появился вопрос: "почему же вы умеете хамить, но не умеете пользоваться поиском". Поиском на форуме я нашёл очень много примеров на тему перевода чисел между разными системами счисления. Но все эти "между разными" сводились к тому, что надо было перевести либо из десятичной, либо в десятичную. И все решения, которые я нашёл, оказывались половинчатыми (т.е. это было то, о чём писалось в разделе 4). При этом несколько раз промелькнула мысль что кто-то где-то видел программу, которая переводит из любой системы счисления в любую, но саму программу я так и не нашёл.

Очень хочется наконец поставить точку в этом вопросе и самому написать эту простую программу. Вообще не в моих правилах писать что-то готовенькое, тем более, что в начале данного раздела я пообещал, что готового решения не будет. Но всё-таки это решение захотелось написать для того, чтобы пальцем показать, что "вот так надо делать, а не так, как делаете вы". Но, исходя из того, что статью ориентирую на тех, кто пытается разобраться в вопросах самостоятельно, программу пишу в максимально примитивном виде на Си. Потому что те, кто всё-таки осилил данный раздел, без проблем разберутся в принципе работы программы такого уровня, а тем, кто ищет халявы, всё равно придётся напрячься и переписать программу под свои нужды (особенно, если преподаватель требует на Си++ или Паскале). Из этих же соображений оставляю программу без комментариев

Но всё-таки если эту программу возьмут ищущие халяву, то хочу предупредить их вот о чём. Если постановка задачи сводится к тому, что надо "преобразовать из десятичной системы счисления в какую-то или из какой-то в десятичную", то преподаватель скорее всего допускает ту же самую ошибку, о которой писалось в разделе 4. Такой преподаватель скорее всего является бестолковым и ожидает "стандартного" решения, описанного в разделе 1, не понимая того, что такое решение НЕ правильное. А приведённая программа покажется ему излишне громоздкой. Но если в задаче сказано, что нужно преобразовать из, например, 7-ричной в 11-ричную, то с большой вероятностью преподаватель грамотный (ну или по крайней мере разбирается конкретно в данном вопросе) и это решение он примет

C
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
/* Данный тип используется для хранения именно внутреннего представления
 * чисел. Обратите внимание на то, в каких местах он используется. В качестве
 * данного типа можно использовать в том числе и библиотечные реализации
 * специальных типов для работы с "большими" числами. Только в этом случае
 * все операции над этим типом преарвтятся в вызовы библиотечных функций */
typedef unsigned long long internal_t;
 
static unsigned
char_to_digit (char c, unsigned radix)
{
  unsigned res;
 
  if (c >= '0' && c <= '9')
    res = c - '0';
  else if (c >= 'a' && c <= 'z')
    res = 10 + (c - 'a');
  else if (c >= 'A' && c <= 'Z')
    res = 10 + (c - 'A');
  else
    abort();
 
  if (res >= radix)
    abort();
 
  return res;
}
 
static char
digit_to_char (unsigned digit)
{
  char res;
 
  if (digit <= 9)
    return '0' + digit;
  else if (digit <= 36)
    return 'a' + (digit - 10);
  else
    abort();
 
  return '\0'; /* avoid warning */
}
 
static internal_t
str_to_internal (const char *str, unsigned radix)
{
  unsigned i;
  internal_t res = 0;
 
  for (i = 0; i < strlen (str); i++)
    {
      res *= radix;
      res += char_to_digit (str[i], radix);
    }
 
  return res;
}
 
static void
internal_to_str (internal_t ival, char *dst, unsigned radix)
{
  char buf[256], *p = &buf[0];
  unsigned r;
 
  do
    {
      r = ival % radix;
      *p++ = digit_to_char (r);
      ival = ival / radix;
    }
  while (ival != 0);
 
  do
    *dst++ = *--p;
  while (p != &buf[0]);
 
  *dst = '\0';
}
 
static void
conv_radix (const char *src_str, unsigned src_radix,
            char *dst_str, unsigned dst_radix)
{
  internal_t ival;
 
  ival = str_to_internal (src_str, src_radix);
  internal_to_str (ival, dst_str, dst_radix);
}
 
int
main (void)
{
  char buf[256];
 
  /* Перевод числа, запись которого в 10-чной форме выглядит как "144"
   * в 16-ичную форму */
  conv_radix ("144", 10, buf, 16);
  printf ("144 в 10-чной = %s в 16-ичной\n", buf);
 
  /* Перевод числа, запись которого в 2-чной форме выглядит как "110011"
   * в 8-ичную форму */
  conv_radix ("110011", 2, buf, 8);
  printf ("110011 в 2-чной = %s в 8-ичной\n", buf);
 
  /* Перевод числа, запись которого в 7-чной форме выглядит как "3602"
   * в 27-ичную форму */
  conv_radix ("3602", 7, buf, 27);
  printf ("3602 в 7-чной = %s в 27-ичной\n", buf);
 
  return 0;
}
*** Update

Оказывается, что программу для перевода чисел я уже писал, но так давно, что об этом уж и позабыл (на форум выложил сравнительно недавно, но саму программу писал очень давно). Возможно, что именно о ней упоминалось в начале раздела 6. Эта программа переводит числа из любой системы счисления в любую БЕЗ сохранения результата во внутреннем машинном представлении (т.е. все операции идут исключительно в строковом виде). Но сам показатель системы счисления (radix) естественным образом задаётся в виде числа, а не строки, потому что хоть что-то должно задаваться в виде числа. При таком раскладе эта программа может работать с числами (строками) любой длины, нужно только обеспечить достаточный размер строковых буферов. По поводу исходника надо сделать замечание, что имя процедуры "conv_dec_to_bin" - это залипший мусор, ибо процедура переводит из любой системы в любую (видимо, забыл переименовать)

Исходник тут

7. Ссылки на темы, где обсуждался данный вопрос
Всего комментариев 4
Комментарии
  1. Старый комментарий
    Аватар для Mikl___
    Возможно, что для программиста на С/Паскале это и так, но пытаясь объяснить студенту изучающему ассемблер перевод из записи числа двоичной/пятеричной/шестнадцатеричной системы счисления в десятеричную систему счисления обычно используют деление числа на число-основание системы счисления и запись остатков с конца, хотя я пытаюсь донести еще несколько способов, допустим мы переводим из Dec в Hex
    1. используем Windows-калькулятор
    2. сперва находим последнюю цифру, затем предпоследнюю и так далее...
      Число 42936 переводится следующим образом:
      42936/16 = 2683 остаток 8
      2683/16 = 167 остаток 11 (по таблице В)
      167/16=10 остаток 7
      10/16=0 остаток 10 (по таблице А) --> 42936=0A7B8h
    3. сперва находим первую цифру, затем вторую и так далее... Для начала придется запомнить степени 16 (165=1048576, 164=65536, 163=4096, 162=256).
      Начинаем с вычисления старшего разряда и определения его порядка в шестнадцатеричном числе, если десятичное число между 1 и 16 миллионами – начинаем с деления на 1048576, если между миллионом и 65 тысячами – начнем с деления на 65536 и так далее. Определившись со степенью n – делим десятичное число на 16n. Результатом будет первая шестнадцатеричная цифра и остаток. Остаток делится на 16n–1 и так далее, пока остаток не станет меньше 16, а степень нулевой. Для примера подсчитаем шестнадцатеричный эквивалент числа 24477:
      24477/4096=5 остаток 3997
      3997/256=15=F остаток 157
      157/16=9 остаток 13
      13/1=13=D--> 24477=5F9Dh
    4. Преобразование целых чисел из восьмеричной системы счисления в десятичную. Чтобы выполнить преобразование, нужно записать данное восьмеричное число, удвоить на k-ом шаге k ведущих разрядов, используя десятичную арифметику, и вычесть полученный результат из (k+1) ведущих разрядов при помощи десятичной арифметики. Если заданное число содержит (m+1) разрядов, то процесс прекращается через m шагов. Для примера преобразуем восьмеричное число 53251218 в десятичное 141985710
      Code
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      
       5.325121
      -1 0           5*2=10
       43.25121
      - 8 6          43*2=86
       346.5121
      - 69 2         346*2=692
       2773.121
      - 554 6        2773*2=5546
       22185.21
      - 4437 0      22185*2=44370
       177482.1
      - 35496 4     177482*2=354964
       141985 7
    Запись от Mikl___ размещена 30.07.2013 в 12:50 Mikl___ вне форума
    Обновил(-а) Mikl___ 30.07.2013 в 13:01
  2. Старый комментарий
    Аватар для Evg
    > Возможно, что для программиста на С/Паскале это и так

    "Это" - это что?

    > ... обычно используют деление числа на число-основание системы счисления и запись
    > остатков с конца, хотя я пытаюсь донести еще несколько способов ...

    > 2. сперва находим последнюю цифру, затем предпоследнюю и так далее

    Так это то же самое

    По поводу способов 3 и 4 я, разумеется, ничего против не имею. Но целью статьи НЕ являлось показать способ преобразования. Основная цель статьи была - показать, в чём отличие между понятиями "число" и "запись числа". Насколько я видел, даже грамотные люди на форуме не все это понимали и не понимали половинчатость своих решений.

    Твои способы 3 и 4 - по сути это тоже половинчатые решения (в контексте озвученной проблемы), т.к. операция деления работает над понятием "число", в то время как на вход задачи подаётся понятие "запись числа". Пока работаешь с 10-чным представлением числа, мозг, как правило, не различает эти понятия в силу обыденности и привычки к 10-чной системе. А потому все три предложенных тобой способа выглядят естественными и понятными. Но из 11-ричной ты так не переведёшь. Точнее, переведёшь, если научишь свой мозг делить столбиком в 11-ричной системе. Что будет эквивалентно реализации операции деления над строковым представлением числа, а это, сам понимаешь, куда более сложная вещь, чем встроенная в язык операция деления над числами (но не над записью числа)
    Запись от Evg размещена 30.07.2013 в 14:56 Evg вне форума
    Обновил(-а) Evg 30.07.2013 в 15:00
  3. Старый комментарий
    Аватар для Evg
    * del (два раза отправилось)
    Запись от Evg размещена 30.07.2013 в 14:56 Evg вне форума
    Обновил(-а) Evg 30.07.2013 в 14:57
  4. Старый комментарий
    Аватар для Mikl___
    • Цитата:
      "Это" - это что?
      Под "это" подразумевалось использование "printf ("Введите число");\scanf ("%d", &val);\printf ("%x\n", val);" использование возможностей языка без детализации (деление, получение модуля, по-символьный вывод)
    • обучение только 2-ому способу
    Запись от Mikl___ размещена 31.07.2013 в 04:26 Mikl___ вне форума
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru