Алгоритмы и структуры данных

Преобразование десятичных чисел в двоичную систему

Понимание того, как переводить десятичные числа (числа, которые мы используем каждый день) в двоичные (используются компьютерами), — одна из основ компьютерных наук. В двоичной системе каждый разряд соответствует определённой степени двойки. Можно представить двоичное число как способ указать, какие именно степени двойки необходимы, чтобы их сумма равнялась заданному числу.
Число в десятичной системе
128
64
32
16
8
4
2
1
Сумма
114
0
1
1
1
0
0
1
0
114 = 64 + 32 + 16 + 2
12
0
0
0
0
1
1
0
0
12 = 8 + 4
13
0
0
0
0
1
1
0
1
13 = 8 + 4 + 1
Каждая 1 в двоичном представлении указывает на то, что соответствующая степень двойки участвует в сумме, а каждая 0 говорит об обратном. Прелесть двоичной системы в её простоте и однозначности.
💡
У каждого числа есть только одно двоичное представление, образованное суммой уникальных степеней двойки.

Нахождение крайнего правого бита

Для начала рассмотрим, как найти крайний правый бит двоичного числа. В десятичной системе, чтобы выделить последнюю цифру числа, достаточно взять остаток от деления на 10 (в программировании это обычно число % 10). Аналогично, в двоичной системе крайний правый бит можно найти, взяв остаток от деления числа на 2 (% 2). Это также означает, что у всех нечётных чисел этот бит равен 1, а у чётных — 0.
Например:
  • Для 114 крайний правый бит равен 0, так как 114 % 2 = 0.
  • Для 13 крайний правый бит равен 1, так как 13 % 2 = 1.

Сдвиг двоичного числа

Когда крайний правый бит найден, следующий шаг — сдвинуть всё двоичное число на один разряд вправо. В десятичном выражении это соответствует целочисленному делению числа на 2 (в большинстве языков программирования — / 2, а в Python — // 2). При таком сдвиге крайний правый бит отбрасывается, а следующий бит становится новым крайним правым.
  • Сдвиг числа 114 (в двоичной форме ) вправо даёт , что соответствует 114 / 2 = 57 в десятичной системе.
  • Сдвиг числа 13 (в двоичной форме ) вправо даёт , что соответствует 13 / 2 = 6 в десятичной системе.

Алгоритм преобразования

Используя операции нахождения крайнего правого бита и его удаления путём сдвига, можно легко составить алгоритм перевода десятичного числа в двоичное:
  1. Инициализировать пустую строку для хранения двоичного представления.
  1. Пока число больше 0:
      • Найти крайний правый бит, взяв остаток при делении на 2.
      • Добавить этот бит слева к строящейся двоичной строке.
      • Сдвинуть число вправо, выполнив целочисленное деление на 2.
  1. Вернуть двоичную строку, если она не пустая, или 0 в противном случае.
С помощью этого алгоритма вы можете перевести любое число из десятичной системы в его уникальное двоичное представление.

Минимальная реализация

b, d = '101001101', 0   # двоичное и десятичное числа
power = 1               # Текущая степень 2 (1, 2, 4, 8, 16, ...)

for bi in b[::-1]:      # Цикл от младшего к старшему биту
    d += int(bi) * power
    power *= 2

print(d)
binary → decimal conversion
b, d = '', 5234         # двоичное и десятичное числа

while d > 0:            # Пока есть биты для обработки
    b = str(d % 2) + b  # Добавляем бит слева от строки
    d //= 2             # Сдвигаем число вправо

print(b if b != '' else 0)
decimal → binary conversion
 
To check your solution you need to sign in
Sign in to continue