Якщо ви шукаєте в Інтернеті How to convert from decimal to binary, ви знайдете чотири прості алгоритми: два для цілих чисел і два для дробів. Вони представлені на прикладах нижче в першій частині статті. Але хоча просто знати алгоритми майже завжди достатньо, я вирішив спробувати зрозуміти, чому вони працюють. У другій частині цієї статті пояснюється основна математика, що лежить в основі кожного з них. Знання цього може допомогти вам запам’ятати будь-який з алгоритмів, якщо ви раптом їх забудете. Я настійно пропоную вам взяти блокнот і ручку і виконувати операції разом зі мною, щоб краще запам’ятати математику. Ось чотири алгоритми з прикладами, які ви можете знайти в Інтернеті.

Перетворення цілого десяткового числа на двійкове

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

Ось приклад такого перетворення з використанням цілого числа 12. Спочатку поділимо число на два, вказавши частку та залишок:

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

Тепер нам просто потрібно виписати залишок у зворотному порядку — 1100. Отже, 12 у десятковій системі представлено як 1100 у двійковій.

Перетворення десяткового дробу в двійковий

Щоб перетворити дріб від 0 до 1 у двійковий, кілька разів помножте дробову частину на 2 і запишіть кожну отриману цілу частину. Прочитайте ці цифри в порядку після двійкової точки. Зупиніться, коли дробова частина дорівнює нулю або коли у вас буде достатньо бітів: такі дроби, як 0,1, вічно повторюються у двійковому форматі.

Ось приклад такого перетворення за допомогою дробу 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}$$

У вас є 4 простих алгоритму, які дозволять вам перетворити двійкові числа в десяткові і назад.

Розкладання числа за основою 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}$$

Перетворення цілого десяткового числа на двійкове

Як виявилося, ми можемо використовувати цю форму розширення base-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 + \frac{1}{2} \\ 1 = 2 \cdot 0 + 1 &\rightarrow 1 : 2 = 0 + \frac{1}{2} \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 і беремо цілу частину під час перетворення дробів у двійкові, я також використовуватиму форму розширення для дробів. Я буду використовувати дробове число 0,375 з першої частини статті. Подібно до цілої частини, давайте уявимо, що не знаємо, як це число представлено у двійковій формі, і запишемо його, замінивши невідомі цифри на x:

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

Як і у випадку з цілими числами, наше завдання полягає в тому, щоб знайти всі x, виділяючи 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 на 1 і записати суму так:

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

Ця скінченна геометрична сума строго менша за 1. Вона наближається до 1 зі збільшенням кількості членів, але ніколи не досягає її для скінченного n. Отже, решта цифр вносять лише дробову частину:

$$0.375 \cdot 2 = x_1 + \underbrace{x_2 \cdot \frac{1}{2} + \ldots + x_n \cdot \frac{1}{2^{n-1}}}_{< 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)))$$

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

Чому не всі дроби можна скінченно представити у двійковому вигляді

Раціональне число має скінченний розклад за основою q, якщо його зменшений знаменник ділить деякий ступінь q. У десятковій системі це означає, що єдиними простими множниками знаменника є 2 і 5; у двійковій системі це має бути ступінь 2. Наприклад, 0,625 можна записати зі знаменником 10³:

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

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

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

Те саме стосується системи base-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. Тут ми також будемо використовувати форму розгортання base-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.375})}_{0.6875}$$ $$\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 у десятковій системі.