Если поискать в интернете How to convert from decimal to binary, вы найдёте четыре простых алгоритма: два для целых чисел и два для дробей. Они приведены с примерами ниже, в первой части статьи. Но хотя знания самих алгоритмов почти всегда достаточно, я решил разобраться, почему они работают. Во второй части статьи объясняется совсем базовая математика, лежащая в основе каждого из них. Понимание её может помочь вам восстановить любой из алгоритмов, если вы вдруг его забудете. Настоятельно советую взять блокнот и ручку и выполнять операции вместе со мной — так математика запомнится лучше. Вот те четыре алгоритма с примерами, которые можно найти в сети.

Перевод десятичного целого в двоичное

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

Вот пример такого перевода на числе 12. Сначала поделим число на два, указывая частное и остаток:

$$\begin{aligned} 12 : 2 &= 6 + 0 \\ 6 : 2 &= 3 + 0 \\ 3 : 2 &= 1 + 1 \\ 1 : 2 &= 0 + 1 \end{aligned}$$

Теперь остаётся выписать остатки в обратном порядке — 1100. Итак, 12 в десятичной системе представляется как 1100 в двоичной.

Перевод десятичной дроби в двоичную

Чтобы перевести дробь в двоичную систему, возьмите исходную дробь и умножьте её на 2, отмечая получившиеся целую и дробную части. Продолжайте умножать на 2, пока получившаяся дробная часть не станет равна нулю. Затем просто выпишите целые части из результатов каждого умножения.

Вот пример такого перевода на дроби 0.375.

$$\begin{aligned} 0.375 \cdot 2 &= 0 + 0.75 \\ 0.75 \cdot 2 &= 1 + 0.5 \\ 0.5 \cdot 2 &= 1 + 0 \end{aligned}$$

Теперь просто выпишем получившуюся целую часть на каждом шаге — 0.011. Итак, 0.375 в десятичной системе представляется как 0.011 в двоичной.

Перевод двоичного целого в десятичное

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

$$\begin{aligned} 2 \cdot 0 + 1 &= 1 \\ 2 \cdot 1 + 0 &= 2 \\ 2 \cdot 2 + 1 &= 5 \\ 2 \cdot 5 + 1 &= 11 \end{aligned}$$

Перевод двоичной дроби в десятичную

Чтобы перевести двоичную дробь в десятичную, начните справа с итога, равного 0. Возьмите текущий итог, прибавьте текущую цифру и разделите результат на 2. Продолжайте, пока цифры не закончатся. Вот пример такого перевода на дроби 0.1011. Деление на 2 я просто заменил умножением на 1/2.

$$\begin{aligned} \frac{1}{2} \cdot (1 + 0) &= 0.5 \\ \frac{1}{2} \cdot (1 + 0.5) &= 0.75 \\ \frac{1}{2} \cdot (0 + 0.75) &= 0.375 \\ \frac{1}{2} \cdot (1 + 0.375) &= 0.6875 \end{aligned}$$

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

Разложение числа по основанию q

Ключ к пониманию того, почему эти алгоритмы работают, — это разложение числа по основанию q. Целое число в любой системе счисления можно представить в следующем виде:

$$N = x_n \cdot q^n + \ldots + x_1 \cdot q^1 + x_0 \cdot q^0$$

где N — целое число, x — цифра (от 0 до 9 для системы по основанию 10, 0 и 1 для системы по основанию 2), q — значение основания (10 для системы по основанию 10, 2 для системы по основанию 2).

Далее в статье эта форма называется разложением числа N по основанию q, или просто разложением по основанию q. Посмотрим, как оно выглядит для числа 12 в десятичной и двоичной системах:

$$\begin{aligned} 12_{10} &= 1 \cdot 10^1 + 2 \cdot 10^0 \\ 1100_2 &= 1 \cdot 2^3 + 1 \cdot 2^2 + 0 \cdot 2^1 + 0 \cdot 2^0 \end{aligned}$$

Точно так же дробное число в любой системе счисления можно представить в следующем виде:

$$N = x_1 \cdot q^{-1} + x_2 \cdot q^{-2} + \ldots + x_n \cdot q^n$$

где N — дробь, x — цифра (от 0 до 9 для системы по основанию 10, 0 и 1 для системы по основанию 2), q — значение основания (10 для системы по основанию 10, 2 для системы по основанию 2).

Для числа 0.375 в десятичной и двоичной системах представление такое:

$$\begin{aligned} 0.375_{10} &= 3 \cdot 10^{-1} + 7 \cdot 10^{-2} + 5 \cdot 10^{-3} \\ 0.011_2 &= 0 \cdot 2^{-1} + 1 \cdot 2^{-2} + 1 \cdot 2^{-3} \end{aligned}$$

Перевод десятичного целого в двоичное

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

$$12_{10} = x_n \cdot 2^n + \ldots + x_1 \cdot 2^1 + x_0 \cdot 2^0$$

Наша задача — найти все x. Посмотрим, что здесь можно сделать. Первое, что нужно заметить: все слагаемые, кроме последнего, будут чётными числами, потому что все они кратны двум. Пользуясь этим, мы можем вывести цифру для x0: если переводимое целое чётное, то x0 равен 0, а если нечётное — то x0 должен быть 1. У нас число 12, оно чётное, значит x0 равен нулю. Запишем это:

$$12_{10} = x_n \cdot 2^n + \ldots + x_1 \cdot 2^1 + 0$$

Дальше нужно найти значение x1. Поскольку все слагаемые от x1 до xN кратны двум, мы можем вынести 2 за скобку, чтобы выделить x1. Сделаем это:

$$12_{10} = 2(\underbrace{x_n \cdot 2^{n-1} + \ldots + x_1 \cdot 2^0}_{6}) + 0$$

Также легко увидеть, что сумма значений внутри скобок равна 6. Значит, наш первый шаг можно записать так:

$$12 = 2 \cdot 6 + 0$$

Продолжим искать остальные x. Многочлен внутри скобок можно выписать отдельным выражением:

$$6_{10} = x_n \cdot 2^{n-1} + \ldots + x_2 \cdot 2^1 + x_1 \cdot 2^0$$

Применяя ту же логику, что и выше, видим, что x1 равен 0. Перепишем это и снова вынесем 2 за скобку:

$$6_{10} = 2 \cdot (\underbrace{x_n \cdot 2^{n-2} + \ldots + x_2 \cdot 2^0}_{3}) + 0$$

Итак, наш второй шаг:

$$6 = 2 \cdot 3 + 0$$

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

$$3_{10} = 2 \cdot (\underbrace{x_n \cdot 2^{n-3} + \ldots + x_3 \cdot 2^0}_{1}) + 1$$

Поскольку частное равно 1, остаётся лишь одно слагаемое, поэтому перепишем предыдущее выражение:

$$3_{10} = 2 \cdot (\underbrace{x_3 \cdot 2^0}_{1}) + 1$$

Итак, наш третий шаг:

$$3 = 2 \cdot 1 + 1$$

В итоге получаем следующее:

$$1_{10} = x_3 \cdot 2^0$$

Понятно, что x3 равен 1. Но поскольку для нашего алгоритма нужно частное, перепишем предыдущее выражение так, чтобы в нём было частное:

$$1_{10} = 2 \cdot 0 + 1$$

Так как мы получили частное 0, работать больше не с чем, и это был наш последний шаг. Выпишем его:

$$1 = 2 \cdot 0 + 1$$

Итак, перевод закончен. Вот как он выглядит по шагам:

$$\begin{aligned} 12 &= 2 \cdot 6 + 0 \\ 6 &= 2 \cdot 3 + 0 \\ 3 &= 2 \cdot 1 + 1 \\ 1 &= 2 \cdot 0 + 1 \end{aligned}$$

Теперь ясно, что остаток на каждом шаге соответствует значению x в соответствующей позиции: первый остаток соответствует первому x, второй остаток — второму x и так далее. Значит, число 12 в двоичной системе по описанному выше алгоритму представляется как 1100.

Напомню, что мы начинали с намерения показать, почему работает алгоритм с делением на 2. Возьмём описанные выше шаги и перенесём 2 в левую часть выражений:

$$\begin{aligned} 12 = 2 \cdot 6 + 0 &\rightarrow 12 : 2 = 6 + 0 \\ 6 = 2 \cdot 3 + 0 &\rightarrow 6 : 2 = 3 + 0 \\ 3 = 2 \cdot 1 + 1 &\rightarrow 3 : 2 = 1 + 1 \\ 1 = 2 \cdot 0 + 1 &\rightarrow 1 : 2 = 0 + 1 \end{aligned}$$

Вот так и видно, как мы пришли к алгоритму, описанному в начале. Расчёты этих четырёх шагов можно также свести в одно представление, вот такое:

$$12 = 2 \cdot (\underbrace{2 \cdot (\overbrace{2 \cdot (\underbrace{2 \cdot 0 + 1}_{1}) + 1 \cdot 2^0}^{3}) + 0 \cdot 2^0}_{6}) + 0 \cdot 2^0$$

Убедитесь, что вы понимаете, как мы получили это представление — оно понадобится, когда мы будем разбирать, как работает алгоритм перевода из двоичной системы в десятичную.

Перевод десятичной дроби в двоичную

Чтобы показать, почему при переводе дробей в двоичную систему мы умножаем на 2 и берём целую часть, я тоже воспользуюсь формой разложения по основанию q — для дробей. Возьму дробное число 0.375 из первой части статьи. Как и с целой частью, представим, будто мы не знаем, как это число записывается в двоичной системе, и выпишем его, заменив неизвестные цифры на x:

$$0.375_{10} = x_1 \cdot 2^{-1} + x_2 \cdot 2^{-2} + \ldots + x_n \cdot 2^n$$

Как и с целыми числами, наша задача — найти все x, выделяя их по одному. Посмотрим, как это сделать. Первое, что стоит заметить: отрицательные степени 2 дают нам дроби со знаменателем 2 в положительных степенях. Перепишем выражение выше:

$$0.375_{10} = x_1 \cdot \frac{1}{2} + x_2 \cdot \frac{1}{2^2} + \ldots + x_n \cdot \frac{1}{2^n}$$

Сразу очевидно, что в правой части выражения можно просто вынести 1/2 за скобку. Сделаем это:

$$0.375_{10} = \frac{1}{2} \cdot (x_1 + x_2 \cdot \frac{1}{2} + \ldots + x_n \cdot \frac{1}{2^{n-1}})$$

а затем перенесём 1/2 в левую часть

$$0.375 \cdot 2 = x_1 + x_2 \cdot \frac{1}{2} + \ldots + x_n \cdot \frac{1}{2^{n-1}}$$

Итак, мы выделили x1 и знаем, что он может быть либо 1, либо 0. Чтобы определить, какая это цифра, посмотрим на остальные слагаемые:

$$x_2 \cdot \frac{1}{2} + \ldots + x_n \cdot \frac{1}{2^{n-1}}$$

Подумаем, насколько большой может быть сумма этих чисел. Если максимальное значение цифр x равно 1, то можно просто заменить x единицами и записать сумму так:

$$\frac{1}{2} + \frac{1}{2^2} + \frac{1}{2^3} + \frac{1}{2^4} + \ldots + \frac{1}{2^n}$$

Что ж, это геометрическая прогрессия из дробей, и сумма такой прогрессии лежит в границах [0 < сумма < 1], так что максимум, который эта сумма может дать, — это 1. Теперь снова посмотрим на наше выражение:

$$0.375 \cdot 2 = x_1 + \underbrace{x_2 \cdot \frac{1}{2} + \ldots + x_n \cdot \frac{1}{2^{n-1}}}_{\text{не более } 1}$$

Теперь должно быть понятно: если правая часть меньше 1, то x1 не может быть равен 1, а значит он равен 0, тогда как остаток равен 0.75.

$$0.375 \cdot 2 = 0 + \underbrace{x_2 \cdot \frac{1}{2} + \ldots + x_n \cdot \frac{1}{2^{n-1}}}_{0.75}$$

Это выглядит в точности как первый шаг алгоритма, приведённого в начале:

$$0.375 \cdot 2 = 0 + 0.75$$

Возьмём дробную часть 0.75 и вынесем ещё одну 1/2, чтобы выделить x2:

$$0.75 = \frac{1}{2} \cdot (x_2 + \ldots + x_n \cdot \frac{1}{2^{n-2}})$$

и перенесём 1/2 влево:

$$\underbrace{0.75 \cdot 2}_{1.5} = x_2 + x_3 \cdot \frac{1}{2} + \ldots + x_n \cdot \frac{1}{2^{n-2}}$$

Теперь, если x2 равен 0, то сумма правой части выражения не может быть больше 1, но левая часть равна 1.5, значит x2 должен быть 1, а остаток — 0.5. Выпишем это:

$$\underbrace{0.75 \cdot 2}_{1.5} = 1 + \underbrace{x_3 \cdot \frac{1}{2} + \ldots + x_n \cdot \frac{1}{2^{n-2}}}_{0.5}$$

И это снова следует схеме алгоритма, приведённого в начале:

$$0.75 \cdot 2 = 1 + 0.5$$

Повторим те же действия для оставшейся дробной части 0.5.

$$\underbrace{0.5 \cdot 2}_{1} = x_3 + \ldots + x_n \cdot \frac{1}{2^{n-3}}$$

По той же логике, что и выше, видим, что x3 равен 1 и дробной части не остаётся:

$$\underbrace{0.5 \cdot 2}_{1} = 1 + \underbrace{\ldots + x_n \cdot \frac{1}{2^{n-3}}}_{0}$$

Поскольку оставшаяся дробная часть равна 0, наш последний шаг выглядит так:

$$0.5 \cdot 2 = 1 + 0$$

Выпишем ещё раз все шаги:

$$\begin{aligned} 0.375 \cdot 2 &= 0 + 0.75 \\ 0.75 \cdot 2 &= 1 + 0.5 \\ 0.5 \cdot 2 &= 1 + 0 \end{aligned}$$

Это в точности тот алгоритм, который я привёл в начале. Как и с целыми числами, расчёты этих трёх шагов можно свести в одно представление:

$$0.375 = \frac{1}{2} \cdot (0 + \frac{1}{2} \cdot (1 + \frac{1}{2} \cdot (1 + 0)))$$

И снова важно полностью ухватить это представление — оно понадобится при разборе перевода из двоичной системы в десятичную.

Почему не все дроби можно конечно представить в двоичной системе

То, что некоторые дроби, конечно представимые в десятичной системе, невозможно конечно представить в двоичной, для многих разработчиков оказывается неожиданностью. Но именно в этой путанице и лежит корень внешне странного результата сложения 0.1 и 0.2. Так что же определяет, можно ли конечно представить дробь в системе счисления? Чтобы число было представимо конечно, знаменатель дроби должен быть степенью основания системы. Например, для системы по основанию 10 знаменатель должен быть степенью 10 — вот почему мы можем конечно представить 0.625 в десятичной системе:

$$\frac{625}{10^3} = 0.625$$

и не можем конечно представить 1/3:

$$\frac{1}{3} = 0.3333\ldots = 0.\overline{3}$$

То же самое и для системы по основанию 2:

$$\frac{625}{1000} = \frac{5}{8} = \frac{5}{2^3}$$

Но если взять 0.1, то знаменатель равен 10, а это не степень 2, значит 0.1 в двоичной системе будет бесконечной дробью. Убедимся в этом с помощью алгоритма, который мы разобрали выше:

$$\begin{aligned} 0.1 \cdot 2 &= 0 + 0.2 \\ 0.2 \cdot 2 &= 0 + 0.4 \\ 0.4 \cdot 2 &= 0 + 0.8 \\ 0.8 \cdot 2 &= 1 + 0.6 \\ 0.6 \cdot 2 &= 1 + 0.2 \\ 0.2 \cdot 2 &= 0 + 0.4 \\ 0.4 \cdot 2 &= 0 + 0.8 \\ &\ldots \end{aligned}$$

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

$$0.1_{10} = 0.00011001100110011\ldots_2 = 0.0\overline{0011}$$

Перевод двоичного целого в десятичное

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

$$1011_2 = 1 \cdot 2^3 + 0 \cdot 2^2 + 1 \cdot 2^1 + 1 \cdot 2^0$$

Поскольку все слагаемые кратны 2, мы можем выносить 2 за скобку, пока частное не станет нулём. Сделаем это:

$$1011_2 = 2 \cdot (2 \cdot (2 \cdot (2 \cdot 0 + 1) + 0) + 1) + 1$$

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

$$11_{10} = 2 \cdot (\underbrace{2 \cdot (\overbrace{2 \cdot (\underbrace{2 \cdot 0 + 1}_{1}) + 0}^{2}) + 1}_{5}) + 1$$ $$\begin{aligned} 2 \cdot 0 + 1 &= 1 \\ 2 \cdot 1 + 0 &= 2 \\ 2 \cdot 2 + 1 &= 5 \\ 2 \cdot 5 + 1 &= 11 \end{aligned}$$

Таким образом, 1011 в двоичной системе — это 11 в десятичной.

Перевод двоичной дроби в десятичную

Вот мы и дошли до последнего алгоритма. Возможно, вы уже сами разобрались в его механике. Если нет — посмотрим, почему он работает. Форма разложения по основанию q и здесь оказывается ключом. Возьмём число 0.1011 из первого раздела. Запишем его в развёрнутом виде:

$$0.1011_2 = 1 \cdot \frac{1}{2} + 0 \cdot \frac{1}{2^2} + 1 \cdot \frac{1}{2^3} + 1 \cdot \frac{1}{2^4}$$

И снова, поскольку все слагаемые кратны 1/2, мы можем выносить 1/2 за скобку, пока не останется дробной части. Сделаем это:

$$0.1011_2 = \frac{1}{2} \cdot (1 + \frac{1}{2} \cdot (0 + \frac{1}{2} \cdot (1 + \frac{1}{2} \cdot (1 + 0))))$$

Соблюдение порядка математических операций даёт алгоритм, описанный в начале:

$$0.6875_{10} = \underbrace{\frac{1}{2} \cdot (1 + \overbrace{\frac{1}{2} \cdot (0 + \frac{1}{2} \cdot (1 + \underbrace{\frac{1}{2} \cdot (1 + 0)}_{0.5}))}^{0.75})}_{0.375}$$ $$\begin{aligned} \frac{1}{2} \cdot (1 + 0) &= 0.5 \\ \frac{1}{2} \cdot (1 + 0.5) &= 0.75 \\ \frac{1}{2} \cdot (0 + 0.75) &= 0.375 \\ \frac{1}{2} \cdot (1 + 0.375) &= 0.6875 \end{aligned}$$

Таким образом, 0.1011 в двоичной системе — это 0.6875 в десятичной.