Двоичная система счисления
Двоичная система счисления — позиционная система счисления с основанием 2. Благодаря непосредственной реализации в цифровых электронных схемах на логических вентилях, двоичная система используется практически во всех современных компьютерах и прочих вычислительных электронных устройствах.
Двоичная запись чисел
В двоичной системе счисления числа записываются с помощью двух символов (0 и 1). Чтобы не путать, в какой системе счисления записано число, его снабжают указателем справа внизу. Например, число в десятичной системе 510, в двоичной 1012. Иногда двоичное число обозначают префиксом 0b или символом & (амперсанд)[1], например 0b101 или соответственно &101.
В двоичной системе счисления (как и в других системах счисления, кроме десятичной) знаки читаются по одному. Например, число 1012 произносится «один ноль один».
Натуральные числа
Натуральное число, записываемое в двоичной системе счисления как [math]\displaystyle{ (a_{n-1} a_{n-2}\dots a_{1} a_0)_2 }[/math], имеет значение:
- [math]\displaystyle{ (a_{n-1} a_{n-2}\dots a_{1} a_0)_2 = \sum_{k=0}^{n-1} a_k 2^k, }[/math]
где:
- [math]\displaystyle{ n }[/math] — количество цифр (знаков) в числе,
- [math]\displaystyle{ a_k }[/math] — значения цифр из множества {0,1},
- [math]\displaystyle{ k }[/math] — порядковый номер цифры.
Отрицательные числа
Отрицательные двоичные числа обозначаются так же как и десятичные: знаком «−» перед числом. А именно, отрицательное целое число, записываемое в двоичной системе счисления [math]\displaystyle{ (- a_{n-1} a_{n-2}\dots a_{1} a_0)_2 }[/math], имеет величину:
- [math]\displaystyle{ (- a_{n-1} a_{n-2}\dots a_{1} a_0)_2 = - \sum_{k=0}^{n-1} a_k 2^k. }[/math]
В вычислительной технике широко используется запись отрицательных двоичных чисел в дополнительном коде.
Дробные числа
Дробное число, записываемое в двоичной системе счисления как [math]\displaystyle{ (a_{n-1} a_{n-2} \dots a_{1} a_{0}, a_{-1} a_{-2} \dots a_{-(m-1)} a_{-m})_2 }[/math], имеет величину:
- [math]\displaystyle{ (a_{n-1} a_{n-2} \dots a_{1} a_{0}, a_{-1} a_{-2} \dots a_{-(m-1)} a_{-m})_2 = \sum_{k=-m}^{n-1} a_k 2^k, }[/math]
где:
- [math]\displaystyle{ m }[/math] — количество цифр дробной части числа,
- [math]\displaystyle{ a_k }[/math] — значения цифр из множества [math]\displaystyle{ \{0,1\} }[/math].
Сложение, вычитание и умножение двоичных чисел
Таблица сложения
+ | 0 | 1 |
---|---|---|
0 | 0 | 1 |
1 | 1 | 0 (перенос 1 в старший разряд) |
Таблица вычитания
- | 0 | 1 |
---|---|---|
0 | 0 | 1 |
1 | 1(заём из старшего разряда) | 0 |
Пример сложения «столбиком» (десятичное выражение 1410 + 510 = 1910 в двоичном виде выглядит как 11102 + 1012 = 100112):
+ | 1 | 1 | 1 | 0 | |
1 | 0 | 1 | |||
1 | 0 | 0 | 1 | 1 |
Таблица умножения
× | 0 | 1 |
---|---|---|
0 | 0 | 0 |
1 | 0 | 1 |
Пример умножения «столбиком» (десятичное выражение 1410 * 510 = 7010 в двоичном виде выглядит как 11102 * 1012 = 10001102):
× | 1 | 1 | 1 | 0 | |||
1 | 0 | 1 | |||||
+ | 1 | 1 | 1 | 0 | |||
1 | 1 | 1 | 0 | ||||
1 | 0 | 0 | 0 | 1 | 1 | 0 |
Преобразование чисел
Для преобразования из двоичной системы в десятичную используют следующую таблицу степеней основания 2:
1024 | 512 | 256 | 128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 |
Начиная с цифры 1 все цифры умножаются на два. Точка, которая стоит после 1, называется двоичной точкой.
Преобразование двоичных чисел в десятичные
Допустим, дано двоичное число 1100012. Для перевода в десятичное запишите его как сумму по разрядам следующим образом:
1 * 25 + 1 * 24 + 0 * 23 + 0 * 22 + 0 * 21 + 1 * 20 = 49
То же самое чуть иначе:
1 * 32 + 1 * 16 + 0 * 8 + 0 * 4 + 0 * 2 + 1 * 1 = 49
Можно записать это в виде таблицы следующим образом:
512 | 256 | 128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 |
1 | 1 | 0 | 0 | 0 | 1 | ||||
+32 | +16 | +0 | +0 | +0 | +1 |
Двигайтесь справа налево. Под каждой двоичной единицей напишите её эквивалент в строчке ниже. Сложите получившиеся десятичные числа. Таким образом, двоичное число 1100012 равнозначно десятичному 4910.
Преобразование дробных двоичных чисел в десятичные
Нужно перевести число 1011010,1012 в десятичную систему. Запишем это число следующим образом:
1 * 26 + 0 * 25 + 1 * 24 + 1 * 23 + 0 * 22 + 1 * 21 + 0 * 20 + 1 * 2−1 + 0 * 2−2 + 1 * 2−3 = 90,875
То же самое чуть иначе:
1 * 64 + 0 * 32 + 1 * 16 + 1 * 8 + 0 * 4 + 1 * 2 + 0 * 1 + 1 * 0,5 + 0 * 0,25 + 1 * 0,125 = 90,875
Или по таблице:
64 | 32 | 16 | 8 | 4 | 2 | 1 | 0.5 | 0.25 | 0.125 | |
1 | 0 | 1 | 1 | 0 | 1 | 0 | , | 1 | 0 | 1 |
+64 | +0 | +16 | +8 | +0 | +2 | +0 | +0.5 | +0 | +0.125 |
Преобразование методом Горнера
Для того, чтобы преобразовывать числа из двоичной в десятичную систему данным методом, надо суммировать цифры слева направо, умножая ранее полученный результат на основу системы (в данном случае 2). Методом Горнера обычно переводят из двоичной в десятичную систему. Обратная операция затруднительна, так как требует навыков сложения и умножения в двоичной системе счисления.
Например, двоичное число 10110112 переводится в десятичную систему так:
0*2 + 1 = 1
1*2 + 0 = 2
2*2 + 1 = 5
5*2 + 1 = 11
11*2 + 0 = 22
22*2 + 1 = 45
45*2 + 1 = 91
То есть в десятичной системе это число будет записано как 91.
Перевод дробной части чисел методом Горнера
Цифры берутся из числа справа налево и делятся на основу системы счисления (2).
Например 0,11012
(0 + 1)/2 = 0,5
(0,5 + 0)/2 = 0,25
(0,25 + 1)/2 = 0,625
(0,625 + 1)/2 = 0,8125
Ответ: 0,11012= 0,812510
Преобразование десятичных чисел в двоичные
Допустим, нам нужно перевести число 19 в двоичное. Вы можете воспользоваться следующей процедурой :
19/2 = 9 с остатком 1
9/2 = 4 c остатком 1
4/2 = 2 без остатка 0
2/2 = 1 без остатка 0
1/2 = 0 с остатком 1
Итак, мы делим каждое частное на 2 и записываем остаток в конец двоичной записи. Продолжаем деление до тех пор, пока в частном не будет 0. Результат записываем справа налево. То есть нижняя цифра (1) будет самой левой и т. д. В результате получаем число 19 в двоичной записи: 10011.
Преобразование дробных десятичных чисел в двоичные
Если в исходном числе есть целая часть, то она преобразуется отдельно от дробной. Перевод дробного числа из десятичной системы счисления в двоичную осуществляется по следующему алгоритму:
- Дробь умножается на основание двоичной системы счисления (2);
- В полученном произведении выделяется целая часть, которая принимается в качестве старшего разряда числа в двоичной системе счисления;
- Алгоритм завершается, если дробная часть полученного произведения равна нулю или если достигнута требуемая точность вычислений. В противном случае вычисления продолжаются над дробной частью произведения.
Пример: Требуется перевести дробное десятичное число 206,116 в дробное двоичное число.
Перевод целой части дает 20610=110011102 по ранее описанным алгоритмам. Дробную часть 0,116 умножаем на основание 2, занося целые части произведения в разряды после запятой искомого дробного двоичного числа:
0,116 • 2 = 0,232
0,232 • 2 = 0,464
0,464 • 2 = 0,928
0,928 • 2 = 1,856
0,856 • 2 = 1,712
0,712 • 2 = 1,424
0,424 • 2 = 0,848
0,848 • 2 = 1,696
0,696 • 2 = 1,392
0,392 • 2 = 0,784
и т. д.
Таким образом 0,11610 ≈ 0,00011101102
Получим: 206,11610 ≈ 11001110,00011101102
Применения
В цифровых устройствах
Двоичная система используется в цифровых устройствах, поскольку является наиболее простой и соответствует требованиям:
- Чем меньше значений существует в системе, тем проще изготовить отдельные элементы, оперирующие этими значениями. В частности, две цифры двоичной системы счисления могут быть легко представлены многими физическими явлениями: есть ток (ток больше пороговой величины) — нет тока (ток меньше пороговой величины), индукция магнитного поля больше пороговой величины или нет (индукция магнитного поля меньше пороговой величины) и т. д.
- Чем меньше количество состояний у элемента, тем выше помехоустойчивость и тем быстрее он может работать. Например, чтобы закодировать три состояния через величину напряжения, тока или индукции магнитного поля, потребуется ввести два пороговых значения и два компаратора,
В вычислительной технике широко используется запись отрицательных двоичных чисел в дополнительном коде. Например, число −510 может быть записано как −1012 но в 32-битном компьютере будет храниться как 111111111111111111111111111110112.
Обобщения
Двоичная система счисления является комбинацией двоичной системы кодирования и показательной весовой функции с основанием равным 2. Число может быть записано в двоичном коде, а система счисления при этом может быть не двоичной, а с другим основанием. Пример: двоично-десятичное кодирование, в котором десятичные цифры записываются в двоичном виде, а система счисления — десятичная.
История
- Полный набор из 8 триграмм и 64 гексаграмм, аналог 3-битных и 6-битных цифр, был известен в древнем Китае в классических текстах книги Перемен. Порядок гексаграмм в книге Перемен, расположенных в соответствии со значениями соответствующих двоичных цифр (от 0 до 63), и метод их получения был разработан китайским учёным и философом Шао Юн в XI веке. Однако нет доказательств, свидетельствующих о том, что Шао Юн понимал правила двоичной арифметики, располагая двухсимвольные кортежи в лексикографическом порядке.
- Индийский математик Пингала (200 год до н. э.) разработал математические основы для описания поэзии с использованием первого известного применения двоичной системы счисления[2][3].
- Прообразом баз данных, широко использовавшихся в Центральных Андах (Перу, Боливия) в государственных и общественных целях в I—II тысячелетии н. э., была узелковая письменность Инков — кипу, состоявшая как из числовых записей десятичной системы[4], так и не числовых записей в двоичной системе кодирования[5]. В кипу применялись первичные и дополнительные ключи, позиционные числа, кодирование цветом и образование серий повторяющихся данных[6]. Кипу впервые в истории человечества использовалось для применения такого способа ведения бухгалтерского учёта, как двойная запись[7].
- Наборы, представляющие собой комбинации двоичных цифр, использовались африканцами в традиционных гаданиях (таких как Ифа) наряду со средневековой геомантией.
- В 1605 году Френсис Бэкон описал систему, буквы алфавита которой могут быть сведены к последовательностям двоичных цифр, которые в свою очередь могут быть закодированы как едва заметные изменения шрифта в любых случайных текстах. Важным шагом в становлении общей теории двоичного кодирования является замечание о том, что указанный метод может быть использован применительно к любым объектам[8] (см. Шифр Бэкона).
- Современная двоичная система была полностью описана Лейбницем в XVII веке в работе Explication de l’Arithmétique Binaire[9]. В системе счисления Лейбница были использованы цифры 0 и 1, как и в современной двоичной системе. Как человек, увлекающийся китайской культурой, Лейбниц знал о книге Перемен и заметил, что гексаграммы соответствуют двоичным числам от 0 до 111111. Он восхищался тем, что это отображение является свидетельством крупных китайских достижений в философской математике того времени[10].
- В 1854 году английский математик Джордж Буль опубликовал знаковую работу, описывающую алгебраические системы применительно к логике, которая в настоящее время известна как Булева алгебра или алгебра логики. Его логическому исчислению было суждено сыграть важную роль в разработке современных цифровых электронных схем.
- В 1937 году Клод Шеннон представил к защите кандидатскую диссертацию Символический анализ релейных и переключательных схем в MIT, в которой булева алгебра и двоичная арифметика были использованы применительно к электронным реле и переключателям. На диссертации Шеннона по существу основана вся современная цифровая техника.
- В ноябре 1937 года Джордж Штибиц, впоследствии работавший в Bell Labs, создал на базе реле компьютер «Model K» (от англ. «Kitchen», кухня, где производилась сборка), который выполнял двоичное сложение. В конце 1938 года Bell Labs развернула исследовательскую программу во главе со Штибицом. Созданный под его руководством компьютер, завершённый 8 января 1940 года, умел выполнять операции с комплексными числами. Во время демонстрации на конференции American Mathematical Society в Дартмутском колледже 11 сентября 1940 года Штибиц продемонстрировал возможность посылки команд удалённому калькулятору комплексных чисел по телефонной линии с использованием телетайпа. Это была первая попытка использования удалённой вычислительной машины посредством телефонной линии. Среди участников конференции, бывших свидетелями демонстрации, были Джон фон Нейман, Джон Мокли и Норберт Винер, впоследствии писавшие об этом в своих мемуарах.
См. также
- Битовые операции
- Степень двойки
- Системы счисления
- Бит
- Байт
- Единицы измерения информации
- Двоичные логические элементы
- Двоичный триггер
- Двоично-десятичный код
- Двоичное кодирование
- Азбука Морзе
Примечания
- ↑ Попова Ольга Владимировна. Учебное пособие по информатике . Дата обращения: 3 ноября 2014. Архивировано 3 ноября 2014 года.
- ↑ Sanchez, Julio & Canton, Maria P. (2007), Microcontroller programming: the microchip PIC, Boca Raton, Florida: CRC Press, с. 37, ISBN 0-8493-7189-9
- ↑ W. S. Anglin and J. Lambek, The Heritage of Thales, Springer, 1995, ISBN 0-387-94544-X
- ↑ Ordish George, Hyams, Edward. The last of the Incas: the rise and fall of an American empire. — New York: Barnes & Noble, 1996. — С. 80. — ISBN 0-88029-595-3.
- ↑ Experts 'decipher' Inca strings . Архивировано 18 августа 2011 года.
- ↑ Carlos Radicati di Primeglio, Gary Urton. Estudios sobre los quipus (неопр.). — С. 49.
- ↑ Dale Buckmaster. The Incan Quipu and the Jacobsen Hypothesis (англ.) // Journal of Accounting Research : journal. — 1974. — Vol. 12, no. 1. — P. 178—181.
- ↑ Bacon, Francis, The Advancement of Learning, vol. 6, London, с. Chapter 1, <http://home.hiwaay.net/~paul/bacon/advancement/book6ch1.html> Архивная копия от 18 марта 2017 на Wayback Machine
- ↑ http://www.leibniz-translations.com/binary.htm Архивная копия от 11 февраля 2021 на Wayback Machine Leibniz Translation.com EXPLANATION OF BINARY ARITHMETIC
- ↑ Aiton, Eric J. (1985), Leibniz: A Biography, Taylor & Francis, с. 245–8, ISBN 0-85274-470-6
Ссылки
- Бинарное счисление // Энциклопедический словарь Брокгауза и Ефрона : в 86 т. (82 т. и 4 доп.). — СПб., 1890—1907.
- Учебное пособие «Арифметические основы ЭВМ и систем». Часть 1. Системы счисления
- Hexadecimal Decimal Binary Octal Converter for programmers Архивная копия от 21 февраля 2011 на Wayback Machine
- Конвертер целых и дробных чисел из двоичной системы счисления в десятичную.
- Фомин С. В. Системы счисления. — М.: Наука, 1987. — 48 с. — (Популярные лекции по математике). (альтернативная ссылка), (альтернативная ссылка на сайт РГБ)
- Системы счисления : методические указания и задание к самостоятельной работе по дисциплине "Информатика" для студентов всех специальностей. — Саратов: Саратовский гос. технический ун-т, 2009. — 24 с.
- Любомудров А.А. Системы счисления. Методы перевода чисел из позиционной системы счисления с основанием p1 в позиционную систему счисления с основанием p2. — М.: НИЯУ МИФИ, 2009. — 28 с.
- Андреева Е. В. Системы счисления и компьютерная арифметика : учеб. пособие. — изд. 3-е. — М.: Бином. Лаб. знаний, 2004. — 254 с.
Системы счисления (16 сент. 2014 г.)
МГИУ : Информатика. Выпуск 1. Системы счисления. (21 февр. 2014 г.)
Двоичная система счисления — визуальное объяснение принципа работы позиционных систем счисления (в частности, двоичной)