Системы счисления. , Перевод чисел из одной в другую.

[@Hgpeu]

Системы счисления

Система счисления - это определенный способ записи чисел и соответствующие ему правила действия над числами.
Системы счисления бывают позиционными и непозиционными.
В позиционной системе счисления величина, которую обозначает цифра в записи числа, зависит от позиции цифры в этом числе. Совокупность различных цифр, используемых в позиционной системе счисления для записи чисел, называется алфавитом системы счисления. Для представления цифр больше 10 используют латинские буквы (А=10, В=11…). Основание системы счисления - это размер алфавита. Число в позиционной системе можно представить в виде суммы произведений составляющих его цифр на соответствующие степени основания системы.

Любая позиционная система вводится следующим образом. Выбирается основание р — целое число и алфавит из р цифр: О, 1, 2, ..., р-1. Тогда любое число Х в этой системе представляется в виде суммы произведений:
Х = а_n*рⁿ + a_n-1*p^n-1 + … + a₀*p⁰
Здесь Х — это число в системе с основанием p, имеющее n+1 цифру в целой части — это цифры из алфавита системы.

Перевод чисел из одной позиционной системы в другую
При переводе чисел из десятичной системы в р-ичную надо разложить десятичное число на слагаемые, содержащие степени числа р. Перевод целого десятичного числа производится путем последовательного деления числа на основание р с выделением остатков от деления до тех пор, пока частное не станет меньше делителя. Выписывая остатки от деления справа налево, получаем р-ричную запись десятичного числа.

Например: переведем (1234)₁₀ в 16-ричное число.
^
| 1234/16=77+2/16 – остаток 2
| 77/16 = 4+1316 – остаток 13. Цифры 13 нет. 13 = D
| 4
Cбор остатков в обратном порядке. Т. е. (1234)₁₀ = (4D2)₁₆
Вот функция реализующая данный алгоритм:

function _10toR(x:longint;R:word):string;
var x,ost:longint;
    s,st,chislo:string;
begin
     repeat
           ost:=x mod R;
           x:=x div R;
           if ost>9 then st:=chr(ord('A')-10+ost)
           else str(ost,st);
           s:=s+st;
     until x=0;
     for i:=1 to length(s) do
     chislo:=chislo+s[length(s)-i+1];
     _10toR:=chislo;
end;

Или 2-й, более простой вариант:

function Convd(x:integer):char;
begin
     if x<10 then Convd:=chr(x+ord('0'))
     else Convd:=Chr(x-10+ord('A'));
end;
function _10toR(N,R:integer):string;
var s:string;
begin
     s:='';
     repeat
           s:=convd(N mod R)+S;
           N:=N div R
     until N=0;
     _10toR:=s;
end;

При переводе чисел из р-ичной системы в десятичную число надо представить в виде суммы произведений представляющих его цифр на соответствующие степени основания системы р.
Например:
(4D2)₁₆ = 4*16² + 13*16¹ + 2*16⁰ = 4*256 + 13 * 16 + 2 = 1024 + 208 + 2 = (1234)₁₀.
210

А эта функция перевода числа из р-ричной системы счисления в 10-чную.

function _Rto10(s:string;R:word):longint;
var z,m,n:integer;
function stepen(x,n:integer):longint;
var k,i:longint;
begin
     k:=1;
     for i:=1 to n do k:=k*x;
     stepen:=k;
end;
begin
     m:=0;
     for i:=1 to length(s) do
     begin
          val(s[i],n,z);
          if z<>0 then n:=10+ord(UpCase(s[i]))-ord('A');
          m:=m+stepen(R,length(s)-i)*n;
     end;
     _Rto10:=m;
end;

Сообщение отредактировано: Romtek - 20.02.05, 13:18

[Some1]

Для тех, кому вообще сложно понять суть систем счисления, я попытаюсь пояснить:
Вот вы всю жизнь пользовались обычными десятичными числами.
Например: 146123656. Это десятичное число. Но почему оно так называется ?
Потому что для обозначения каждой циферки используется 10 различных значков. Это: 0, 1, 2, 3, 4, 5, 6, 7, 8 и 9.

А теперь попробуйте себе представить, что этих значков не 10, как мы привыкли, а к примеру 11:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9 и A.
Одиннадцатью значками тоже можно написать любое число. Но просто мы привыкли, что если число больше 10, то мы писали сначала цифру - сколько в это число входит десяток, а потом писали цифру - остаток.

Например для числа 27 мы пишем - 27 %) это значит что в этом числе 2 десятки, и 7 единиц.
Можно это число записать в другой системе счисления, в которой всё основано не на количестве десяток (10), сотен (10*10), тысяч (10*10*10) в числе, а на количестве (к примеру) одиннадцаток (11), 121иннадцаток (11*11), 1331иннадцаток (11*11*11).

Вот десятичная система: 35 это 3 десятки и 5 единиц
Вот одиннадцатиричная система: 35 это 3 одиннадцатки и 2 единицы. То есть в 11ричной системе это же число будет записано как 32 (три по 11 и ещё 2).
Давайте попробуем это-же число записать в восьмиричной системе. В этой системе не существует чисел, больше чем 7.
Просто нельзя использовать значки 8 и 9. Пользуясь тем же принципом определили, что в числе 35 можно вместить 4 восьмёрки. 4 восьмёрки это 32. значит у нас ещё остаётся 3. Значит число 35 в восьмиричной системе записывается как 43 %)))
Это конечно не сложно %) правда ? %))

Но давайте усложним задачу. Давайте переведём в 8миричную систему число 350.
сначала узнаем последнюю цифру: 350/8=43 а остаток будет 6. Это и есть последняя цифра искомого числа. тоесть если 43 умножить на 8 а затем прибавить 6, то мы получим 350.
Теперь посмотрим предпоследнюю цифру: 43/8=5 и остаток 3. Значит предпоследней цифрой будет 3. Ну а ещё одной предпредпоследней цифрой будет число 5, так как 43/8=5, а 5 - уже меньше чем 8. Итак получим число 536. Это число 350, записанное в восьмиричной системе.

Чтобы ещё попрактиковаться давайте попробуем перевести число 733 в 21ричную систему.
В этой системе будет 21 разный значок для обозначения чисел. А мы знаем только 10 (0-9). Остальные числа не имеют значков. В математике принято обозначать недостающие числа буквами английского алфавита.
Вот так: 0-0,1-1,2-2,3-3,4-4,5-5,6-6,7-7,8-8,9-9,10-A,11-B,12-C,13-D,14-E,15-F,16-G,17-H,18-I,19-J,20-K. (и всё. всего 21 знак, если считать нолик).
Значит если в этой системе нам нужно записать число 20, то мы запишем его знаком "К", если число 15 - знаком "F".
Приступим к переводу числа: 733/21=34, и 19 в остатке. 19 будет последней цифрой искомого числа, но в 21ричной системе оно будет обозначаться знаком "J".
Ищем предпоследний знак: 34/21=1 и в остатке 13. Число 13 в 21ричной системе обозначается знаком "D", и этот знак будет предпоследней цифрой искомого числа.
Предпредпоследний или первый знак в данном случае получается 1, так как 1 уже меньше чем 21.
В 21ричной системе число 1 так и записывается, знаком 1.
В итоге число 733 в 21ричной системе будет выглядеть как 1DJ.

Вы, возможно, спросите, зачем всё это нужно?

Я могу объяснить, зачем это понадобилось. Когда были придуманы компьютеры, люди столкнулись с тем, что очень сложно записывать в компьютер различные числа десятичного формата, как раз привычного нам. Потому, что в системе электроники довольно сложно создать автомат, который мог бы хранить десять различных уровней напряжения. А только так можно хранить в памяти информацию. Гораздо проще в электронике создать такое устройство, которое может хранить в себе два напряжения - либо напряжение есть, либо его нет. То есть, иметь два состояния. Другими словами это число 0, или число 1. Поэтому нужно было сделать так, чтобы привычные нам числа в десятичной системе (745, или 12326348123) хранились в памяти компьютера в последовательности нулей и единиц. Если представить какое либо десятичное число в таком варианте, имея достаточное количество устройств, позволяющих хранить в себе два состояния (0 - нет напряжения и 1 - есть напряжение) можно было бы записать любое число.

Значит нужно было придумать систему, позволяющую переводить десятичные числа в последовательность нулей и единиц. Вот для этого и были использованы системы счисления. В памяти компьютера любое число записано в двоичной системе счисления. Она формируется так же как и выше описанные системы, на которых мы недавно практиковались. В этой системе есть только два числа - 0 или 1. И любое число при помощи записи в двоичном формате можно представить в виде последовательности нулей и единиц, а затем занести в память компьютера.

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

Зачем нужны другие системы счисления кроме двоичных?
Давайте я опишу следующую задачу, которая могла бы возникнуть.
К примеру у нас есть 7 источников света. Каждый источник света может светить разными цветами:
не светить (чёрный), синий, красный, зелёный, жёлтый, белый. Всего 6 состояний.
Цветом каждого источника мы можем управлять с пульта управления. Нам необходимо узнать, сколько может быть вариантов, при которых бы горели жёлтым цветом сразу три источника.

Эта задача решается перебором. Если бы вы пробовали решить её вручную, вы бы начали перебирать все состояния источников цвета, считая попутно, когда загорались бы сразу три жёлтых.
На компьютере эту задачу решить можно проще, введя новую систему счисления.
Давайте введём 6тиричную систему счисления.
То есть, каждая цифра этой системы может иметь 6 различных значений. И запомним для себя, что каждое из этих значений для нас будет значить один из цветов - 0-чёрный, 1-синий, 2-красный, 3-зелёный, 4-жёлтый, 5-белый. - всего 6 значений (считая ноль).

Тогда 7 источников света в нашей задаче можно описать семью цифрами шестиричной системы счисления. Например: 0534412
Эта цифра может для нас значить, что первая лампа не светит (чёрный цвет), вторая лампа светит белым цветом, третья лампа светит зелёным, четвёртая и пятая лампы светят жёлтым цветом, шестая - синим и наконец седьмая лампа светит красным цветом.

Так вот, если написать программу, которая эмулирует шестиричную систему счисления, то можно шестиричным числом описать наши семь ламп, и их состояния.
Теперь если перебирать последовательно все шестиричные цифры от 0000000 до 5555555, можно получить все варианты в которых можно зажигать наши источники света.
Напрмер:

Цитата

0000000 0000001 0000002 0000003 0000004 0000005
0000010 0000011 0000012 0000013 0000014 0000015
0000020 0000021 0000022 0000023 0000024 0000025
0000030 0000031 0000032 0000033 0000034 0000035
0000040 0000041 0000042 0000043 0000044 0000045
0000050 0000051 0000052 0000053 0000054 0000055

0000100 0000101 0000102 0000103 0000104 0000105
0000110 0000111 0000112 0000113 0000114 0000115
0000120 0000121 0000122 0000123 0000124 0000125
0000130 0000131 0000132 0000133 0000134 0000135
0000140 0000141 0000142 0000143 0000144 0000145
0000150 0000151 0000152 0000153 0000154 0000155

0000200 0000201 0000202 0000203 0000204 0000205
0000210 0000211 0000212 0000213 0000214 0000215
0000220 0000221 0000222 0000223 0000224 0000225
0000230 0000231 0000232 0000233 0000234 0000235
0000240 0000241 0000242 0000243 0000244 0000245
0000250 0000251 0000252 0000253 0000254 0000255

И так далее

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

Сообщение отредактировано: volvo877 - 30.04.08, 05:54

[progalex]

Может немного повторюсь, но....


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

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

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

Каждая СС использует конкретный алфавит, с помощью которого она представляет числа в виде определенной совокупности символов, а именно цифр:0,1,2,3,4,5,6,7,8,9 -- и букв латинского алфавита:A,B,C,D,...,Z. Самыми распространенными СС являются двоичная (0,1), шестнадцатиричная (0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F), восьмиричная (0,1,2,3,4,5,6,7), ну и конечно десятичная(0,1,2,3,4,5,6,7,8,9), которой мы пользуемся каждый день.
Применение
Двоичная СС очень широко используется в различного вида ЭВМ и подобных им машинах, чтобы, например, определять, идет ли электрический сигнал(1) или не идет(0).
Шестнадцатеричная СС очень широко используется программистами, так как из нее очень легко переводить числа в двоичную систему.
Восьмеричная система так же используется в основном программистами и операторами ЭВМ, так как она также удобна для перевода в двоичную СС, но используется гораздо реже.

Способы перевода чисел из одних систем счисления в другие.
Определим основные правила перевода чисел из одной системы счисления в другую.

1. При переводе числа произвольной СС в 10-ую СС нужно воспользоваться всего лишь одной формулой, которую, конечно, Вам нужно знать: An=a_n-1*q^n-1+a_n-2*q^n-2+...+a₁*q¹+a₀*q⁰+a_-1*q^-1+...+a_m-1*q^m-1 .
2. При переводе в СС отличную от десятичной нужно следовать следующим правилам:
   
   Последовательно делим данное нам число и получаемое целое частное на основание СС в которую мы хотим перевести, до тех пор пока частное не станет равным 0.
   Полученные остатки выразить алфавитом (набор символов, которые образуют числа нужной нам СС) нужной СС.
   Составить число в новой СС, начиная с последнего остатка.
3. При переводе дробных чисел из одной СС в другую нужно следовать следующим правилам:
   Последовательно умножаем дробную часть данного числа на основание нужной нам СС до тех пор пока дробная часть не станет равной 0(или до нужной степени точности, так как не всегда частное может стать равным 0).При получении целой части ее отбрасываем.
   Полученные целые части произведений являются числами новой СС.
   Составить дробную часть числа в новой системе, начиная с целой части первого произведения.
4. Для быстрого перевода чисел из шестнадцатиричной и восьмеричной СС в двоичную, нужно следовать следовать следующем правилу:
   
   переводим каждую цифру данного нам числа в СС используя следущую таблицу:
   

   -------------------------------------------------------------------
   | Десятичная  |  Двоичная   |  Восьмеричная  |  Шестнадцатиричная  |
   -------------------------------------------------------------------
   |      0      |     0       |         0      |         0           |
   |      1      |     1       |         1      |         1           |
   |      2      |     10      |         2      |         2           |
   |      3      |     11      |         3      |         3           |
   |      4      |     100     |         4      |         4           |
   |      5      |     101     |         5      |         5           |
   |      6      |     110     |         6      |         6           |
   |      7      |     111     |         7      |         7           |
   |      8      |     1000    |         10     |         8           |
   |      9      |     1001    |         11     |         9           |
   |      10     |     1010    |         12     |         0A          |
   |      11     |     1011    |         13     |         0B          |
   |      12     |     1100    |         14     |         0C          |
   |      13     |     1101    |         15     |         0D          |
   |      14     |     1110    |         16     |         0E          |
   |      15     |     1111    |         17     |         0F          |
   --------------------------------------------------------------------

5. При переводе из двоичной СС в шестнадцатиричную или восьмеричную используем следующие правила:
   для шестнадцатеричной
   разбиваем данное нам двоичное число на тетрады(по четыре цифры), начиная с конца (например,
   110010111=0001 1001 0111), и переводим каждую тетраду согласно таблице, приведенной выше, а затем из полученных цифр составляем число в том же порядке как цифры выглядят тетрадами
   для восьмеричной
   разбиваем данное нам двоичное число на триады(по три цифры), начиная с конца (например,
   1110010111=001 110 010 111), и переводим каждую триаду согласно таблице, приведенной выше, а затем из полученных чисел составляем число в том же порядке как цифры выглядят триадами.

Вот наверно и все, что можно сказать о переводе чисел из одной СС в другую.

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

---

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

Начнем с описания переменных, которые нам понадобятся. Переменные a и b соответственно обозначают основание СС, из которой нужно перевести и в которую нужно перевести, переменная r будет хранить в себе остатки от деления, cc - число в десятичной СС, с которым, собственно, и будет проходить основная работа, с - число, которое мы вводим, ab - число, которое мы должны получить после перевода, так как в системах счисления с основанием >10 присутствуют латинские буквы, то эти переменные имеет строковый тип данных, dd - число, которое служит связью десятичной СС с другой СС:

var a,b,cc,r:integer;c,ab,dd:string;

В основу нашего алгоритма мы положим то, что компьютер не понимает, в какой СС записана информация, он понимает, что если содержание переменной является числовым типом информации, то она записана в десятичной форме, поэтому мы будем введенное нами число переводить в десятичную СС, но хранить его в строковой переменной. Перевод в десятичную СС переводиться посредством формулы, описанной выше. Все действия производятся внутри цикла while, внутри него отделяется от числа по цифре, начиная с конца. Так как в качестве цифр у нас могут быть латинские буквы, то каждой букве должно соответствовать фиксированное число десятичной СС, а я буду работать с ASCII кодами символов, то мы поставим условие, является ли цифра числом или латинской буквой, так как ASCII коды латинских букв и чисел (0,1,..,9) являются не последовательными.

Function sn (a, n: integer): integer; { функция возведения в степень }
 
Var i,s: integer;
Begin
  sn := 0;
  s := 1;
  For i:=1 To n Do
    s := s*a;
  sn := s;
End;
 
Procedure make_to_ten (m: String; Var kk: String); { процедура перевода числа в десятичную СС }
var
  i, r : integer;
  l : char;
Begin
  i := 0;
  r := 0;
  while i<>length(m) Do
  Begin
    l := m[length(m)-i];              {отделяем цифру}
    If ord(l)<=ord('9') Then
       r := r + (ord(l) - ord('0')) * sn (a, i)    {для чисел 0,1,..,9}
    Else
       r := r + (ord(l) - ord('a') + 10) * sn (a, i); {для латинских букв}
    i := i + 1;
  End;
  str (r, kk);
End;

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

Function intg(d:String): integer;
 
Var code,res: integer;
Begin
  val(d,res,code);
  intg := res;
End;
(*------------------------------------------
  остальные процедуры и функции + интерфейс
  ------------------------------------------*)
ab := '';
If b=10 Then make_to_ten(c,ab) {переводим в десятичную СС}
        Else
          Begin
            make_to_ten(c,dd); {переводим в десятичную СС}
            cc := intg(dd);      {переводим строковую информацию в целочисленную}
            while cc>0 Do
            Begin
              r := cc Mod b;  {берем остаток}
              cc := cc Div b; {берем целое частное}
              If r>=10 Then ab := chr(ord('a')+r-10)+ab
              Else ab := chr(48+r)+ab;
            End;
          End;

Еще хочу добавить, что в программе основание системы счисления может быть варьироваться от 2 до 36, так как число латинских букв - 26, а цифр - 10. Так что Вы можете поставить ограничение в своей программе.

Сообщение отредактировано: volvo877 - 30.04.08, 05:56

[Romtek]

Наиболее встречающиеся варианты перевода из одной системы счисления в другую:

(*
Function Dec2Hex (num: Word): String;  { перевод из 10-ичной в 16-ичную }
Function Dec2Bin (num: word): String;  { перевод из 10-ичной в 2-ичную }
Function Hex2Dec (hs:string): longint; { перевод из 16-ичной в 10-ичную }
Function Bin2Dec (S: String): longint; { перевод из 2-ичной в 10-ичную }
*)
 
Function Dec2Hex (num: Word): String;
var result: string;
    remainder: word;
    c: char;
begin
     result := '';
     while num <> 0 do
     begin
          remainder := num mod 16;
          num := num div 16; { или  num := num shr 4 }
          if remainder < 10 then
             c := chr (remainder + ord ('0'))
          else
             c := chr (remainder + ord ('A') - 10);
          result := c + result;
     end;
     Dec2Hex := '$' + result
end;
 
Function Dec2Bin (num: word): String;
var result: string;
    remainder: word;
    c: char;
begin
     result := '';
     while num <> 0 do
     begin
          remainder := num mod 2;
          num := num div 2; { или num := num shr 1 }
          c := chr (remainder + ord ('0'));
          result := c + result;
     end;
     Dec2Bin := result
end;
 
Function Hex2Dec (hs:string): longint;
var
  res,k: longint;
  r,i: word;
  c: char;
begin
       res := 0;
       k := 1;
       for i := length (hs) downto 1 do
       begin
            c := UpCase (hs[i]);
            case c of
            'A'..'F': r := ord(c) - (ord('A') - 10);    { ord (c) - 55 }
            '0'..'9': r := ord(c) - ord('0');           { ord (c) - 48 }
            else break
            end;
            inc (res, r * k); { res := res + r * k}
            k := k * 16; { или k := k shl 4 }
       end;
       Hex2Dec := res;
end;
 
Function Bin2Dec (S: String): longint;
var
  i, bit: word;
  p, result: longint;
Begin
       result := 0;
       p := 1;
       for i := length (S) downto 1 do
       begin
            bit := ord (S[i]) - ord ('0');
            inc (result, bit * p);
            p := p * 2;                    { или   p := p shl 1 }
       end;
       Bin2dec:=result;
End;
 
begin
     writeln (dec2bin (2004));
     writeln (dec2hex (2004));
     writeln (hex2dec ('fff0'));
     writeln (bin2dec ('11111010100'))
end.

Сообщение отредактировано: Romtek - 20.02.05, 13:28