Системы счисления в программировании и универсальный алгоритм

В информатике в основном используются системы счисления с основанием степени 2, а в языке Python есть ряд встроенных функций, которые позволяют переводить число в 2, 8, 16-ричные системы, и возвращать число в любую систему обратно в 10-ичную.

• bin(x) – преобразование целого числа в двоичную строку;
• oct(х) – преобразование целого числа в восьмеричную строку;
• hex(х) –преобразование целого числа в шестнадцатеричную строку;
• int([object], [основание системы счисления]) – преобразование к целому числу в указанной системе счисления.

Давайте попробуем с помощью функций перевести число 35 в двоичную, восьмеричную и шестнадцатеричную системы счисления:

a1 = bin(35)

a2 = oct(35)

a3 = hex(35)

print(a1,a2,a3)

Результат выполнения программы:

0b100011 0o43 0x23

Вроде бы все верно, однако, что это еще за префиксы «0b», «0o», «0x»?

 
На самом деле все просто: достаточно просто ответить на вопрос: как понять в какой системе счисления было выведено число? Именно для этого и пишется префикс-сокращение:

• 0b – bin – двоичная
• 0o – oct – восьмеричная
• 0x – hex – шестнадцатеричная

 
Для корректного использования данного числа, нужно сделать срез со второго символа (напоминаю, что эти команды возвращают строку): 

a1 = str(bin(35))

a2 = str(oct(35))

a3 = str(hex(35))

print(a1[2:],a2[2:],a3[2:])

Результат выполнения программы: 

100011  43  23

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

a1 = int('100011',2)

a2 = int('43',8)

a3 = int('23',16)

print(a1,a2,a3)

Результат выполнения программы:

И вуаля, все работает, получаем обратно наше число 35, которое и вводили изначально. 

Но возникает вопрос: что же делать, если мне нужно перевести, например, в 7-ричную систему счисления? Для этого нам потребуется написать программу, потому что таких функций в python нет, а в других языках нет даже стандартных, поэтому давайте разбираться:

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

То есть, чтобы узнать на что оканчивается число в десятичной системе счисления, достаточно просто поделить его на 10 и взять остаток:

56 mod 10 = 6
394 mod 10 = 4
3 mod 10 = 3

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

56 div 10 = 5
394 div 10 = 39
3 div 10 = 0

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

56 = 111000;               56 mod 2 = 0
394 = 110001010;      394 mod 2 = 0
3 = 11;                        3 mod 2 = 1

Нам лишь остается собрать все цифры, чтобы получить итоговое число, и перевернуть его, потому что остаток от деления – это цифра с конца.

1. Через строку;
2. Через число.

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

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

В программе для примера используется перевод числа 35. Его можно изменить, поменяв число в строке x = 35. А перевод осуществляется в двоичную систему счисления. Его можно осуществлять в любую, достаточно просто изменить все цифры 2 в программе на нужное основание.

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