Двоичная система для чайников. Часть 2.⁠⁠

Здравствуйте, товарищи!

Для лучшего понимания сути данного поста желательно сначала прочитать
первую часть.

Я решил сделать серию постов по информатике для чайников. Это второй пост.
Ставьте лайки, если хотите еще немного лампового ликбеза ;)

---------------------------------------------------------

Перевод из десятичной системы в двоичную

Как я говорил ранее, любое десятичное число можно разбить на сумму вида

а*10^0 + b*10^1 + c*10^2 + d*10^3 +...

где a, b, c, d - это числа от 0 до 9.

Точно так же, любое двоичное число можно записать как сумму вида

а*2^0 + b*2^1 + c*2^2 + d*2^3 +...

где a, b, c, d - это 0 или 1.

Таким образом, перевод числа из одной системы в другую состоит в подборе этих самых коэффициентов a, b, с, d и т.д.

Давайте переведём число 185 в двоичную систему.

Очевидно (надеюсь), что нет смысла рассматривать степени двойки большие нашего числа (185) нет смысла. В данном случае нет смысла рассматривать числа от 2^8 (=256) и более.

Соответственно, нам надо найти максимальную степень двойки, которая меньше или равна числу, с которым мы работаем. В данном случае это 2^7 (=128).

Получаем:

185 = 1 * 2^7 + x

где x - это остаток, который нам еще предстоит разобрать.

Находим x:

x = 185 - 2^7 = 185 - 128 = 57

Теперь имеем:

185 = 1 * 2^7 + 57

Дальше нам надо применить тот же алгоритм к полученному хвосту:

57 = 1 * 2^5 + x1 = 1 * 2^5 + 25

И дальше:

25 = 1 * 2^4 + x2 = 1 * 2^4 + 9

9 = 1 * 2^3 + x3 = 1 * 2^3 + 1

1 = 1 * 2^0

Теперь соберём все "хвосты" вместе:

185 = 1 * 2^7 + 1 * 2^5 + 1 * 2^4 + 1 * 2^3 + 1 * 2^0

Давайте оценим, сколько цифр будет в нашем двоичном числе.

Максимальная степень двойки получилась 7.

Соответственно, всего получим 7+1 цифр (т.к. считаем степени с нулевой), наглядно:

76543210

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

76543210 - это номер позиции (соответствует степени двойки)

10111001 - а это наш ответ (185 в двоичной системе)

Проверим результат обратным преобразованием:

10111001 => 1 * 2^7 + 0 * 2^6 + 1 * 2^5 + 1 * 2^4 + 1 * 2^3 + 0 * 2^2 + 0 * 2^1 + 1 * 2^0

уберём все нулевые слагаемые и получим

10111001 => 1 * 2^7 + 1 * 2^5 + 1 * 2^4 + 1 * 2^3 + 1 * 2^0

Теперь посчитаем всё это дело и получим:

10111001 => 185

Вот как-то так.

Интересный факт.

Все мы знаем, что, чтобы умножить число на десять, достаточно просто приписать к нему справа нолик.

234*10 = 2340

А чтобы поделить на десять (если нас не интерисует дробная часть, конечно), достаточно убрать последнюю цифру:

234/10 = 23 (и 4 в остатке).

Точно так же можно делать и в двоичной системе, только умножать и делить не на десять, а на два:

1101 * 10 = 11010 (напоминаю: это запись в двоичной системе)

1101 / 10 = 110

Этот приём иногда применяют в программах для ускорения вычислений.

Небольшое теоретическое обоснование

У некоторых может всплыть такой вопрос: почему при разложении числа на степени двойки не может оказаться, что какой-то степени будет больше, чем одна?

Объясняю. Допустим, у нас есть число в котором 2^7 помещается два раза, т.е. это получается 2*2^7, а это уже равно 2^8.

Всё :)