Двоичное число

Двоичное число — это число, выраженное в по основанию -2 системе счисления или в двоичной системе счисления , метод представления чисел используются только два символа , в котором для натуральных чисел : обычно «0» ( ноль ) и «1» ( единица ). Двоичное число может также относиться к рациональному числу , которое имеет конечное представление в двоичной системе счисления, то есть частное целого числа по степени двойки.

Система счисления с основанием 2 представляет собой систему счисления с основанием 2 позиционную . Каждая цифра называется битом или двоичной цифрой. Из-за своей простой реализации в цифровых электронных схемах с использованием логических элементов двоичная система используется почти всеми современными компьютерами и компьютерными устройствами в качестве предпочтительной системы использования по сравнению с различными другими человеческими методами связи из-за простоты язык и помехоустойчивость в физической реализации.

История

Современная двоичная система счисления изучалась в Европе в 16-17 веках Томасом Харриотом , Хуаном Карамуэлем-и-Лобковицем и Готфридом Лейбницем . Однако системы, связанные с двоичными числами, появились ранее во многих культурах, включая древний Египет, Китай и Индию.

Египет

Смотрите также: Древнеегипетская математика

Считается, что арифметические значения были представлены частями Ока Гора.

Писцы Древнего Египта использовали две разные системы для своих дробей: египетские дроби (не связанные с двоичной системой счисления) и дроби Глаза Гора (названные так потому, что многие историки математики считают, что символы, используемые для этой системы, можно расположить так, чтобы они образовывали глаз Гора , хотя это оспаривается). Дроби Глаза Гора — это двоичная система счисления дробных количеств зерна, жидкостей или других мер, в которой доля хеката выражается как сумма двоичных дробей 1/2, 1/4, 1/8, 1. /16, 1/32 и 1/64. Ранние формы этой системы можно найти в документах Пятой династии Египта , примерно 2400 г. до н.э., а ее полностью развитая иероглифическая форма относится к Девятнадцатой династии Египта , примерно 1200 г. до н.э.

Метод умножения в Древнем Египте также тесно связан с двоичными числами. В этом методе умножение одного числа на второе выполняется с помощью последовательности шагов, в которых значение (первоначально первое из двух чисел) либо удваивается, либо к нему снова добавляется первое число; Порядок выполнения этих шагов определяется двоичным представлением второго числа. Использование этого метода можно увидеть, например, в Математическом папирусе Ринда , датируемом примерно 1650 годом до нашей эры.

Китай

Даосский багуа

« И Цзин» датируется 9 веком до нашей эры в Китае. Двоичная система счисления в И-Цзин используется для интерпретации четвертичной техники гадания .

В его основе лежит даосская двойственность Инь и Ян . Восемь триграмм (багуа) и набор из 64 гексаграмм («шестьдесят четыре» гуа) , аналогичные трехбитным и шестибитным двоичным числам, использовались, по крайней мере, еще во времена династии Чжоу в древнем Китае .

Ученый династии Сун (1011–1077) переставил гексаграммы в формат , Шао Юн напоминающий современные двоичные числа, хотя он не намеревался использовать свое расположение математически. Просмотр младшего бита поверх одиночных гексаграмм в квадрате Шао Юна и чтение по строкам либо снизу справа вверху слева со сплошными линиями как 0 и пунктирными линиями как 1, либо сверху слева вниз справа со сплошными линиями как 1 и пунктирными линиями как 0 гексаграмм можно интерпретировать как последовательность от 0 до 63.

Индия

Индийский учёный Пингала (ок. II в. до н. э.) разработал двоичную систему описания просодии . Он описал метры в виде кратких и долгих слогов (последний равен по длине двум коротким слогам). Они были известны как лагху (легкие) и гуру (тяжелые) слоги.

Индуистская классика Пингалы под названием «Чандахшастра» (8.23) описывает формирование матрицы, чтобы придать уникальное значение каждому метру. «Чандахшастра» буквально переводится с санскрита как наука о метрах . Двоичные представления в системе Пингалы увеличиваются вправо, а не влево, как в двоичных числах современной позиционной записи . В системе Пингалы числа начинаются с единицы, а не с нуля. Четыре коротких слога «0000» являются первым шаблоном и соответствуют значению один. Числовое значение получается добавлением единицы к сумме значений мест .

Другие культуры

Жители острова Мангарева во Французской Полинезии до 1450 года использовали гибридную двоично- десятичную систему. Щелевые барабаны с бинарными тонами используются для кодирования сообщений в Африке и Азии. Наборы бинарных комбинаций, подобные И Цзин, также использовались в традиционных африканских системах гадания, таких как Ифа, а также в средневековой западной геомантии . В большинстве языков коренных народов Австралии используется система с основанием 2.

Западные предшественники Лейбница

В конце 13 века Рамон Лулль задался целью объяснить всю мудрость во всех отраслях человеческого знания того времени. С этой целью он разработал общий метод или «Ars Generalis», основанный на двоичных комбинациях ряда простых базовых принципов или категорий, благодаря чему его считают предшественником информатики и искусственного интеллекта.

В 1605 году Фрэнсис Бэкон обсудил систему, с помощью которой буквы алфавита можно было свести к последовательностям двоичных цифр, которые затем можно было закодировать как едва заметные варианты шрифта в любом случайном тексте. Что важно для общей теории двоичного кодирования, он добавил, что этот метод можно использовать с любыми объектами вообще: «при условии, что эти объекты способны различаться только в два раза; как колокола, трубы, фонари и факелы, отчет мушкетов и любых подобных инструментов». (См. шифр Бэкона .)

В 1617 году Джон Нэпьер описал систему, которую он назвал арифметикой местоположения , предназначенную для выполнения двоичных вычислений с использованием непозиционного представления букв. Томас Харриот исследовал несколько позиционных систем счисления, в том числе двоичную, но не опубликовал свои результаты; позже они были найдены среди его бумаг. Возможно, первая публикация системы в Европе была сделана Хуаном Карамуэлем-и-Лобковицем в 1700 году.

Лейбниц и «И Цзин»

Готфрид Лейбниц

Лейбниц изучал двоичную нумерацию в 1679 году; его работа опубликована в его статье Explication de l'Arithmétique Binaire (опубликованной в 1703 году). Полное название статьи Лейбница переводится на английский язык как «Объяснение двоичной арифметики, в которой используются только символы 1 и 0, с некоторыми замечаниями о ее полезности и о том, какой свет она проливает на древние китайские фигуры Фу Си » . Система Лейбница использует 0 и 1, как и современная двоичная система счисления. Пример двоичной системы счисления Лейбница следующий:

0 0 0 1 числовое значение 2 ⁰

0 0 1 0 числовое значение 2 ¹

0 1 0 0 числовое значение 2 ²

1 0 0 0 числовое значение 2 ³

Во время переписки со священником-иезуитом Иоахимом Буве в 1700 году, который стал знатоком И Цзин , будучи миссионером в Китае, Лейбниц объяснил свою двоичную систему счисления, а Буве в своих письмах 1701 года продемонстрировал, что И Цзин был независимым, параллельным изобретением. двоичной записи. Лейбниц и Буве пришли к выводу, что эта карта свидетельствует о крупных достижениях Китая в философской математике, которой он восхищался. Об этом параллельном изобретении Либниц написал в своем «Объяснении двоичной арифметики», что «это восстановление их значения после такого большого промежутка времени покажется тем более любопытным».

Это отношение было центральной идеей его универсальной концепции языка или характеристики универсальной , популярной идеи, которой внимательно следовали его преемники, такие как Готтлоб Фреге и Джордж Буль, в формировании современной символической логики . Лейбниц впервые познакомился с « И Цзин» благодаря контакту с французским иезуитом Иоахимом Буве , который посетил Китай в 1685 году в качестве миссионера. Лейбниц рассматривал гексаграммы И Цзин как подтверждение универсальности его собственных религиозных убеждений как христианина. Двоичные числа занимали центральное место в теологии Лейбница. Он считал, что двоичные числа символизируют христианскую идею creatio ex nihilo или творения из ничего.

[Концепция, которую] нелегко передать язычникам, — это творение ex nihilo всемогущей силой Бога. Теперь можно сказать, что ничто в мире не может лучше представить и продемонстрировать эту силу, чем происхождение чисел, как оно представлено здесь через простое и неприукрашенное представление Единицы и Ноля или Ничего.

- Письмо Лейбница герцогу Брауншвейгскому с И Цзин . гексаграммами

Более поздние события

Джордж Буль

В 1854 году британский математик Джордж Буль опубликовал знаковую статью, подробно описывающую алгебраическую систему логики , которая впоследствии стала известна как булева алгебра . Его логические расчеты сыграли важную роль в разработке цифровых электронных схем.

В 1937 году Клод Шеннон защитил магистерскую диссертацию в Массачусетском технологическом институте , в которой впервые в истории реализовал булеву алгебру и двоичную арифметику с использованием электронных реле и переключателей. озаглавленная «Символический анализ релейных и коммутационных схем» Диссертация Шеннона, цифровых схем . , по сути, положила начало практическому проектированию

В ноябре 1937 года Джордж Стибиц , тогда работавший в Bell Labs , завершил работу над релейным компьютером, который он назвал «Модель К» (от « Кухни », где он его собрал), который выполнял вычисления с помощью двоичного сложения. В конце 1938 года Bell Labs санкционировала полноценную исследовательскую программу под руководством Стибица. Их компьютер комплексных чисел, завершенный 8 января 1940 года, был способен вычислять комплексные числа . Во время демонстрации на конференции Американского математического общества в Дартмутском колледже 11 сентября 1940 года Стибиц смог отправлять дистанционные команды калькулятору комплексных чисел по телефонным линиям с помощью телетайпа . Это была первая вычислительная машина, когда-либо использовавшаяся удаленно по телефонной линии. Некоторыми участниками конференции, ставшими свидетелями демонстрации, были Джон фон Нейман , Джон Мокли и Норберт Винер , написавший об этом в своих мемуарах.

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

Представительство

Любое число может быть представлено последовательностью битов (двоичных цифр), которая, в свою очередь, может быть представлена ​​любым механизмом, способным находиться в двух взаимоисключающих состояниях. Любую из следующих строк символов можно интерпретировать как двоичное числовое значение 667:

1	0	1	0	0	1	1	0	1	1
|	―	|	―	―	|	|	―	|	|
☒	☐	☒	☐	☐	☒	☒	☐	☒	☒
и	н	и	н	н	и	и	н	и	и

Двоичные часы могут использовать светодиоды для выражения двоичных значений. В этих часах каждый столбец светодиодов показывает двоично-десятичное число традиционного шестидесятеричного времени.

Числовое значение, представленное в каждом случае, зависит от значения, присвоенного каждому символу. На заре вычислительной техники для представления двоичных значений использовались переключатели, перфорированные отверстия и перфоленты. В современном компьютере числовые значения могут быть представлены двумя разными напряжениями ; на магнитном диске . магнитную полярность можно использовать Состояние «положительное», « да » или «включено» не обязательно эквивалентно числовому значению единицы; это зависит от используемой архитектуры.

В соответствии с общепринятым представлением цифр арабскими цифрами , двоичные числа обычно записываются с использованием символов 0 и 1 . При написании двоичные цифры часто имеют индексы, префиксы или суффиксы, обозначающие их основу или систему счисления . Следующие обозначения эквивалентны:

• 100101 двоичный (явное указание формата)
• 100101b (суффикс, обозначающий двоичный формат; также известный как соглашение Intel )
• 100101B (суффикс, указывающий двоичный формат)
• bin 100101 (префикс, указывающий двоичный формат)
• 100101 ₂ (нижний индекс, обозначающий систему счисления по основанию 2 (двоичная))
• %100101 (префикс, обозначающий двоичный формат; также известный как соглашение Motorola). )
• 0b100101 (префикс, обозначающий двоичный формат, распространенный в языках программирования)
• 6b100101 (префикс, указывающий количество битов в двоичном формате, распространенный в языках программирования)
• #b100101 (префикс, обозначающий двоичный формат, распространенный в языках программирования Lisp)

При произношении двоичные числа обычно читаются по цифрам, чтобы отличить их от десятичных чисел. Например, двоичное число 100 произносится как один ноль , а не как сто , чтобы сделать его двоичную природу явной и в целях корректности. Поскольку двоичная цифра 100 представляет собой число четыре, было бы неправильно называть это число сотней (слово, которое представляет совершенно другое значение или сумму). Альтернативно, двоичная цифра 100 может быть прочитана как «четыре» (правильное значение ), но это не делает явным ее двоичную природу.

Считаем в двоичном формате

Десятичный число	Двоичный число
0	0
1	1
2	10
3	11
4	100
5	101
6	110
7	111
8	1000
9	1001
10	1010
11	1011
12	1100
13	1101
14	1110
15	1111

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

Десятичный счет

Десятичный счет использует десять символов от 0 до 9 . Счет начинается с постепенной замены младшей значащей цифры (крайней правой цифры), которую часто называют первой цифрой . Когда доступные символы для этой позиции исчерпаны, младшая цифра сбрасывается в 0 , а следующая цифра более высокой значимости (на одну позицию влево) увеличивается ( переполнение ), и возобновляется инкрементная замена младшей цифры. Этот метод сброса и переполнения повторяется для каждой значимой цифры. Подсчет происходит следующим образом:

000, 001, 002, ... 007, 008, 009 (самая правая цифра сбрасывается на ноль, а цифра слева от нее увеличивается)

0 1 0, 011, 012, ...

   ...

090, 091, 092, ... 097, 098, 099 (две крайние справа цифры сбрасываются на нули, а следующая цифра увеличивается)

1 00, 101, 102, ...

Двоичный счет

Этот счетчик показывает, как считать в двоичном формате от нуля до тридцати одного.

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

Двоичный подсчет следует той же процедуре, и снова постепенная замена начинается с младшей двоичной цифры или бита (крайнего правого, также называемого первым битом только два символа 0 и 1 ), за исключением того, что доступны . Таким образом, после того, как бит достигает 1 в двоичном формате, приращение сбрасывает его в 0, но также вызывает приращение следующего бита слева:

0000,

000 1 , (крайний правый бит начинается сначала, а следующий бит увеличивается)

00 1 0, 0011, (два крайних правых бита начинаются сначала, а следующий бит увеличивается)

0 1 00, 0101, 0110, 0111, (три крайних правых бита начинаются сначала, а следующий бит увеличивается)

1 000, 1001, 1010, 1011, 1100, 1101, 1110, 1111 ...

В двоичной системе каждый бит представляет возрастающую степень 2, причем самый правый бит представляет 2. ⁰ , следующий представляет 2 ¹ , тогда 2 ² , и так далее. Значение двоичного числа представляет собой сумму степеней 2, представленных каждым битом «1». Например, двоичное число 100101 преобразуется в десятичную форму следующим образом:

100101 ₂ = [ ( 1 ) × 2 ⁵ ] + [ ( 0 ) × 2 ⁴ ] + [ ( 0 ) × 2 ³ ] + [ ( 1 ) × 2 ² ] + [ ( 0 ) × 2 ¹ ] + [ ( 1 ) × 2 ⁰ ]

100101 ₂ = [ 1 × 32 ] + [ 0 × 16 ] + [ 0 × 8 ] + [ 1 × 4 ] + [ 0 × 2 ] + [ 1 × 1 ]

100101 ₂ = 37 ₁₀

Фракции

Дроби в двоичной арифметике заканчиваются, только если 2 — единственный простой делитель в знаменателе . В результате 1/10 не имеет конечного двоичного представления ( 10 имеет простые делители 2 и 5 ). Это приводит к тому, что 10 × 1/10 не будет точно равно 1 в двоичной арифметике с плавающей запятой . Например, для интерпретации двоичного выражения 1/3 = .010101... это означает: 1/3 = 0 × 2. ⁻¹ + 1 × 2 ⁻² + 0 × 2 ⁻³ + 1 × 2 ⁻⁴ + ... = 0,3125 + ... Точное значение невозможно найти с помощью суммы конечного числа обратных степеней двойки, нули и единицы в двоичном представлении 1/3 вечно чередуются.

Фракция	Десятичный	Двоичный	Дробное приближение
1/1	1   или   0,999...	1   или   0. 1	1/2 + 1/4 + 1/8...
1/2	0,5   или   0,4999...	0,1   или   0,0 1	1/4 + 1/8 + 1/16 . . .
1/3	0.333...	0. 01	1/4 + 1/16 + 1/64 . . .
1/4	0,25   или   0,24999...	0,01   или   0,00 1	1/8 + 1/16 + 1/32 . . .
1/5	0,2   или   0,1999...	0. 0011	1/8 + 1/16 + 1/128 . . .
1/6	0.1666...	0.001 01	1/8 + 1/32 + 1/128 . . .
1/7	0.142857142857...	0. 001	1/8 + 1/64 + 1/512 . . .
1/8	0,125   или   0,124999...	0,001   или   0,000 1	1/16 + 1/32 + 1/64 . . .
1/9	0.111...	0. 000111	1/16 + 1/32 + 1/64 . . .
1/10	0,1   или   0,0999...	0.0 0011	1/16 + 1/32 + 1/256 . . .
1/11	0.090909...	0. 0001011101	1/16 + 1/64 + 1/128 . . .
1/12	0.08333...	0.0001 01	1/16 + 1/64 + 1/256 . . .
1/13	0.076923076923...	0. 000100111011	1/16 + 1/128 + 1/256 . . .
1/14	0.0714285714285...	0.0 001	1/16 + 1/128 + 1/1024 . . .
1/15	0.0666...	0. 0001	1/16 + 1/256 . . .
1/16	0,0625   или   0,0624999...	0,0001   или   0,0000 1	1/32 + 1/64 + 1/128 . . .

Двоичная арифметика

Арифметика в двоичной системе во многом похожа на арифметику в других позиционных системах счисления . С двоичными числами можно выполнять сложение, вычитание, умножение и деление.

Добавление

Основная статья: Adder (электроника)

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

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

0 + 0 → 0

0 + 1 → 1

1 + 0 → 1

1 + 1 → 0, переносим 1 (поскольку 1 + 1 = 2 = 0 + (1 × 2 ¹ ) )

При сложении двух цифр «1» получается цифра «0», а в следующий столбец нужно будет добавить 1. Это похоже на то, что происходит в десятичной системе счисления, когда складываются определенные однозначные числа; если результат равен или превышает значение системы счисления (10), цифра слева увеличивается:

5 + 5 → 0, переносим 1 (поскольку 5 + 5 = 10 = 0 + (1 × 10 ¹ ) )

7 + 9 → 6, переносите 1 (поскольку 7 + 9 = 16 = 6 + (1 × 10 ¹ ) )

Это известно как перенос . Когда результат сложения превышает значение цифры, процедура заключается в том, чтобы «перенести» лишнее количество, разделенное по системе счисления (то есть 10/10), влево, прибавив его к следующему позиционному значению. Это правильно, поскольку следующая позиция имеет вес, больший в коэффициент, равный основанию. Перенос в двоичном формате работает так же:

  1 1 1 1 1    (carried digits)
    0 1 1 0 1
+   1 0 1 1 1
-------------
= 1 0 0 1 0 0 = 36

В этом примере складываются две цифры: 01101 ₂ (13 ₁₀ ) и 10111 ₂ (23 ₁₀ ). В верхнем ряду показаны используемые биты переноса. Начиная с крайнего правого столбца, 1 + 1 = 10 ₂ . 1 переносится влево, а 0 записывается внизу самого правого столбца. Добавляется второй столбец справа: 1 + 0 + 1 = 10 ₂ снова; переносится 1, а внизу пишется 0. Третий столбец: 1 + 1 + 1 = 11 ₂ . На этот раз переносится 1, а в нижнем ряду пишется 1. Подобная процедура дает окончательный ответ 100100 ₂ (36 ₁₀ ).

Когда компьютеры должны сложить два числа, действует правило: x xor y = (x + y) mod 2 для любых двух битов x и y также можно выполнить очень быстрые вычисления.

Метод длительного переноса

Упрощением многих задач двоичного сложения является «метод длительного переноса» или «метод двоичного сложения Брукхауса». Этот метод особенно полезен, когда одно из чисел содержит длинный набор единиц. Он основан на простой предпосылке, что в двоичной системе, если дан набор цифр, полностью состоящий из n единиц (где n — любая целая длина), добавление 1 приведет к числу 1, за которым следует строка n нулей. Эта концепция логически следует так же, как и в десятичной системе, где добавление 1 к строке n девяток приведет к числу 1, за которым следует строка н 0с:

     Binary                        Decimal
    1 1 1 1 1     likewise        9 9 9 9 9
 +          1                  +          1
  ———————————                   ———————————
  1 0 0 0 0 0                   1 0 0 0 0 0

Такие длинные строки довольно часто встречаются в двоичной системе. Отсюда следует, что большие двоичные числа можно складывать в два простых шага без чрезмерных операций переноса. В следующем примере две цифры складываются вместе: 1 1 1 0 1 1 1 1 1 0 ₂ (958 ₁₀ ) и 1 0 1 0 1 1 0 0 1 1 ₂ (691 ₁₀ ), используя традиционный метод переноса. слева и метод длинного переноса справа:

Traditional Carry Method                       Long Carry Method
                                vs.
  1 1 1   1 1 1 1 1      (carried digits)   1 ←     1 ←            carry the 1 until it is one digit past the "string" below
    1 1 1 0 1 1 1 1 1 0                       1 1 1 0 1 1 1 1 1 0  cross out the "string",
+   1 0 1 0 1 1 0 0 1 1                   +   1 0 1 0 1 1 0 0 1 1  and cross out the digit that was added to it
———————————————————————                    ——————————————————————
= 1 1 0 0 1 1 1 0 0 0 1                     1 1 0 0 1 1 1 0 0 0 1

В верхнем ряду показаны используемые биты переноса. Вместо стандартного переноса из одного столбца в другой может быть добавлена ​​цифра «1» наименьшего порядка с «1» в соответствующем разряде под ней, а «1» может быть перенесена на одну цифру после конца столбца. ряд. «Использованные» номера необходимо вычеркнуть, так как они уже добавлены. Другие длинные строки также могут быть отменены с использованием того же метода. Затем просто сложите оставшиеся цифры обычным способом. Действуя таким образом, вы получите окончательный ответ: 1 1 0 0 1 1 1 0 0 0 1 ₂ (1649 ₁₀ ). В нашем простом примере с использованием небольших чисел традиционный метод переноса требовал восьми операций переноса, тогда как метод длинного переноса требовал только двух, что представляет собой существенное сокращение усилий.

Таблица сложения

	0	1
0	0	1
1	1	10

Таблица двоичного сложения похожа, но не совпадает с таблицей истинности операции логической дизъюнкции . $\lor$. Разница в том, что $1\lor 1=1$, пока $1+1=10$.

Вычитание

Дополнительная информация: представления чисел со знаком и дополнение до двух.

Вычитание работает примерно так же:

0 − 0 → 0

0 − 1 → 1, одолжить 1

1 − 0 → 1

1 − 1 → 0

Вычитание цифры «1» из цифры «0» дает цифру «1», а 1 нужно будет вычесть из следующего столбца. Это известно как заимствование . Принцип тот же, что и при переноске. Когда результат вычитания меньше 0, наименьшего возможного значения цифры, процедура состоит в том, чтобы «одолжить» дефицит, разделенный на систему счисления (то есть 10/10) слева, вычитая его из следующего позиционного числа. ценить.

    *   * * *   (starred columns are borrowed from)
  1 1 0 1 1 1 0
−     1 0 1 1 1
----------------
= 1 0 1 0 1 1 1

  *             (starred columns are borrowed from)
  1 0 1 1 1 1 1
–   1 0 1 0 1 1
----------------
= 0 1 1 0 1 0 0

Вычитание положительного числа эквивалентно добавлению равного отрицательного числа абсолютного значения . Компьютеры используют знаковые представления чисел для обработки отрицательных чисел — чаще всего в виде дополнения до двух . Такие представления устраняют необходимость в отдельной операции «вычитания». Используя обозначение дополнения до двух, вычитание можно резюмировать следующей формулой:

А - В = А + не В + 1

Умножение

Умножение в двоичном формате аналогично десятичному аналогу. Два числа А и B можно умножить на частичные произведения: для каждой цифры в B , произведение этой цифры в А вычисляется и записывается на новой строке, сдвинутой влево так, чтобы ее крайняя правая цифра совпадала с цифрой в Б, который был использован. Сумма всех этих частичных произведений дает окончательный результат.

Поскольку в двоичной системе только две цифры, есть только два возможных результата каждого частичного умножения:

• Если цифра в B равен 0, частичное произведение также равно 0
• Если цифра в B равен 1, частичное произведение равно А

Например, двоичные числа 1011 и 1010 умножаются следующим образом:

           1 0 1 1   (A)
         × 1 0 1 0   (B)
         ---------
           0 0 0 0   ← Corresponds to the rightmost 'zero' in B
   +     1 0 1 1     ← Corresponds to the next 'one' in B
   +   0 0 0 0
   + 1 0 1 1
   ---------------
   = 1 1 0 1 1 1 0

Двоичные числа также можно умножать на биты после двоичной точки :

               1 0 1 . 1 0 1     A (5.625 in decimal)
             × 1 1 0 . 0 1       B (6.25 in decimal)
             -------------------
                   1 . 0 1 1 0 1   ← Corresponds to a 'one' in B
     +           0 0 . 0 0 0 0     ← Corresponds to a 'zero' in B
     +         0 0 0 . 0 0 0
     +       1 0 1 1 . 0 1
     +     1 0 1 1 0 . 1
     ---------------------------
     =   1 0 0 0 1 1 . 0 0 1 0 1 (35.15625 in decimal)

См. также алгоритм умножения Бута .

Таблица умножения

	0	1
0	0	0
1	0	1

Таблица двоичного умножения аналогична таблице истинности логического соединения . операции $\land$.

Разделение

См. Также: Алгоритм деления § Целочисленное деление (без знака) с остатком.

Длинное деление в двоичном формате снова аналогично десятичному аналогу.

В приведенном ниже примере делитель равен 101 ₂ или 5 в десятичном виде, а делимое — 11011 ₂ или 27 в десятичном виде. Процедура такая же, как и при делении десятичной дроби в столбик ; здесь делитель 101 ₂ входит в первые три цифры 110 ₂ делимого один раз, поэтому в верхней строке записана «1». Этот результат умножается на делитель и вычитается из первых трех цифр делимого; следующая цифра («1») включается для получения новой трехзначной последовательности:

              1
        ___________
1 0 1   ) 1 1 0 1 1
        − 1 0 1
          -----
          0 0 1

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

             1 0 1
       ___________
1 0 1  ) 1 1 0 1 1
       − 1 0 1
         -----
             1 1 1
         −   1 0 1
             -----
             0 1 0

Таким образом, частное 11011 _2, разделенное на 101 ₂ , равно 101 ₂ , как показано в верхней строке, а остаток, показанный в нижней строке, равен 10 ₂ . В десятичной системе это соответствует тому, что 27 разделить на 5 равно 5 с остатком 2.

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

Квадратный корень

Процесс извлечения двоичного квадратного корня по цифрам такой же, как и из десятичного квадратного корня, и объясняется здесь . Пример:

             1 0 0 1
            ---------
           √ 1010001
             1
            ---------
      101     01 
               0
             --------
      1001     100
                 0
             --------
      10001    10001
               10001
              -------
                   0

Побитовые операции

Основная статья: Побитовая операция

Хотя это и не связано напрямую с числовой интерпретацией двоичных символов, последовательностями битов можно манипулировать с помощью логических логических операторов . Когда строка двоичных символов обрабатывается таким образом, это называется побитовой операцией ; логические операторы AND , OR и XOR могут выполняться над соответствующими битами двух двоичных чисел, предоставленных в качестве входных данных. Логическую операцию НЕ можно выполнить над отдельными битами одного двоичного числа, предоставленного в качестве входных данных. Иногда такие операции могут использоваться в качестве арифметических сокращений, а также могут иметь другие вычислительные преимущества. Например, арифметический сдвиг двоичного числа влево эквивалентен умножению на (положительную, целую) степень 2.

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

Десятичное число в двоичное

Преобразование (357) ₁₀ в двоичную запись приводит к (101100101)

с основанием 10 Чтобы преобразовать целое число в его эквивалент с основанием 2 (двоичный), число делится на два . Остаток — это наименее значимый бит . Частное снова делится на два; его остаток становится следующим наименее значащим битом. Этот процесс повторяется до тех пор, пока не будет достигнуто частное, равное единице. Последовательность остатков (включая последнее частное единицы) образует двоичное значение, поскольку каждый остаток должен быть либо нулем, либо единицей при делении на два. Например, (357) ₁₀ выражается как (101100101) _2.

Двоичный код в десятичный

Преобразование из основания 2 в основание 10 просто инвертирует предыдущий алгоритм. Биты двоичного числа используются один за другим, начиная со старшего (крайнего левого) бита. Начиная со значения 0, предыдущее значение удваивается, а затем добавляется следующий бит для получения следующего значения. Это можно организовать в виде таблицы с несколькими столбцами. Например, чтобы преобразовать 10010101101 ₂ в десятичное число:

Предыдущее значение	× 2 +	Следующий бит	= Следующее значение
0	× 2 +	1	= 1
1	× 2 +	0	= 2
2	× 2 +	0	= 4
4	× 2 +	1	= 9
9	× 2 +	0	= 18
18	× 2 +	1	= 37
37	× 2 +	0	= 74
74	× 2 +	1	= 149
149	× 2 +	1	= 299
299	× 2 +	0	= 598
598	× 2 +	1	= 1197

Результат: 1197 ₁₀ . Первое приоритетное значение, равное 0, представляет собой просто начальное десятичное значение. Этот метод является применением схемы Горнера .

Двоичный	1	0	0	1	0	1	0	1	1	0	1
Десятичный	1×2 10 +	0×2 9 +	0×2 8 +	1×2 7 +	0×2 6 +	1×2 5 +	0×2 4 +	1×2 3 +	1×2 2 +	0×2 1 +	1×2 0 =	1197

Дробные части числа преобразуются аналогичными методами. Они снова основаны на эквивалентности сдвига с удвоением или делением пополам.

В дробном двоичном числе, таком как 0.11010110101 ₂ , первая цифра равна ${\textstyle {\frac {1}{2}}}$, второй ${\textstyle ({\frac {1}{2}})^{2}={\frac {1}{4}}}$и т. д. Итак, если на первом месте после запятой стоит 1, то число не меньше ${\textstyle {\frac {1}{2}}}$, и наоборот. Удвоение этого числа равно как минимум 1. Это предполагает алгоритм: несколько раз удваивайте преобразуемое число, записывайте, равен ли результат хотя бы 1, а затем выбрасывайте целую часть.

Например, ${\textstyle ({\frac {1}{3}})_{10}}$в двоичном формате это:

Преобразование	Результат
${\textstyle {\frac {1}{3}}}$	0.
${\textstyle {\frac {1}{3}}\times 2={\frac {2}{3}}<1}$	0.0
${\textstyle {\frac {2}{3}}\times 2=1{\frac {1}{3}}\geq 1}$	0.01
${\textstyle {\frac {1}{3}}\times 2={\frac {2}{3}}<1}$	0.010
${\textstyle {\frac {2}{3}}\times 2=1{\frac {1}{3}}\geq 1}$	0.0101

Таким образом, повторяющаяся десятичная дробь 0,3 ... эквивалентна повторяющейся двоичной дроби 0,01 ....

Или, например, 0,1 ₁₀ в двоичном формате:

Преобразование	Результат
0.1	0.
0,1 × 2 = 0,2 <1	0.0
0,2 × 2 = 0,4 <1	0.00
0,4 × 2 = 0,8 <1	0.000
0.8 × 2 = 1.6 ≥ 1	0.0001
0.6 × 2 = 1.2 ≥ 1	0.00011
0,2 × 2 = 0,4 <1	0.000110
0,4 × 2 = 0,8 <1	0.0001100
0.8 × 2 = 1.6 ≥ 1	0.00011001
0.6 × 2 = 1.2 ≥ 1	0.000110011
0,2 × 2 = 0,4 <1	0.0001100110

Это тоже повторяющаяся двоичная дробь 0,0 0011 ... . Может показаться неожиданным, что конечные десятичные дроби могут иметь повторяющиеся расширения в двоичном формате. Именно по этой причине многие с удивлением обнаруживают, что 1/10+...+1/10 (сложение 10 чисел) отличается от 1 в двоичной арифметике с плавающей запятой . Фактически, единственные двоичные дроби с завершающими расширениями имеют форму целого числа, деленного на степень 2, чего не является 1/10.

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

$${\begin{aligned}x&=&1100&.1{\overline {01110}}\ldots \\x\times 2^{6}&=&1100101110&.{\overline {01110}}\ldots \\x\times 2&=&11001&.{\overline {01110}}\ldots \\x\times (2^{6}-2)&=&1100010101\\x&=&1100010101/111110\\x&=&(789/62)_{10}\end{aligned}}$$

Другой способ преобразования из двоичного формата в десятичный, часто более быстрый для человека, знакомого с шестнадцатеричным , — сделать это косвенно — сначала преобразовать ( $x$ в двоичном формате) в ( $x$ в шестнадцатеричном формате), а затем конвертировать ( $x$ в шестнадцатеричном формате) в ( $x$ в десятичном формате).

Для очень больших чисел эти простые методы неэффективны, поскольку они выполняют большое количество операций умножения или деления, когда один операнд очень велик. Простой алгоритм «разделяй и властвуй» асимптотически более эффективен: данное двоичное число делится на 10. ^к , где k выбрано так, чтобы частное примерно равнялось остатку; затем каждая из этих частей преобразуется в десятичную, и они объединяются . Учитывая десятичное число, его можно разделить на две части примерно одинакового размера, каждая из которых преобразуется в двоичную форму, после чего первая преобразованная часть умножается на 10. ^к и добавляется ко второй преобразованной части, где k — количество десятичных цифр во второй, наименее значимой части перед преобразованием.

Шестнадцатеричный

Основная статья: Шестнадцатеричный

0 шестнадцатеричный	=	0 дек	=	0 окт.		0	0	0	0
1 шестигранник	=	1 дек.	=	1 окт.		0	0	0	1
2 шестигранника	=	2 дек.	=	2 окт.		0	0	1	0
3 шестигранника	=	3 дек.	=	3 окт.		0	0	1	1
4 шестигранника	=	4 дек.	=	4 окт.	0	1	0	0
5 шестигранников	=	5 дек	=	5 окт.	0	1	0	1
6 шестигранников	=	6 дек	=	6 окт.	0	1	1	0
7 шестигранников	=	7 декабря	=	7 окт.	0	1	1	1
8 шестигранников	=	8 дек	=	10 окт.	1	0	0	0
9 шестигранников	=	9 дек	=	11 окт.	1	0	0	1
шестигранник ​	=	10 дек.	=	12 окт.	1	0	1	0
B шестигранник	=	11 дек	=	13 окт.	1	0	1	1
С шестнадцатеричный	=	12 дек	=	14 окт.	1	1	0	0
D шестигранник	=	13 дек	=	15 окт.	1	1	0	1
Е шестнадцатеричный	=	14 дек	=	16 окт.	1	1	1	0
F шестигранник	=	15 дек	=	17 окт.	1	1	1	1

Двоичный формат можно легко преобразовать в шестнадцатеричный формат и обратно. Это связано с тем, что система счисления шестнадцатеричной системы (16) является степенью системы счисления двоичной системы (2). Точнее, 16 = 2 ⁴ , поэтому для представления одной цифры шестнадцатеричного числа требуются четыре двоичных цифры, как показано в соседней таблице.

Чтобы преобразовать шестнадцатеричное число в его двоичный эквивалент, просто замените соответствующие двоичные цифры:

3А ₁₆ = 0011 1010 ₂

Е7 ₁₆ = 1110 0111 ₂

Чтобы преобразовать двоичное число в его шестнадцатеричный эквивалент, разделите его на группы по четыре бита. Если количество битов не кратно четырем, просто вставьте дополнительные 0 бит слева (так называемое дополнение ). Например:

1010010 ₂ = 0101 0010 сгруппированы с заполнением = 52 ₁₆

11011101 ₂ = 1101 1101 сгруппировано = ДД ₁₆

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

C0E7 ₁₆ = (12 × 16 ³ ) + (0 × 16 ² ) + (14 × 16 ¹ ) + (7 × 16 ⁰ ) = (12 × 4096) + (0 × 256) + (14 × 16) + (7 × 1) = 49,383 ₁₀

Восьмеричный

Основная статья: Октал

Двоичная система также легко преобразуется в восьмеричную систему счисления, поскольку в восьмеричной системе счисления используется система счисления 8, которая представляет собой степень двойки (а именно, 2 ³ , поэтому для представления восьмеричной цифры требуется ровно три двоичных цифры). Соответствие между восьмеричными и двоичными числами такое же, как и для первых восьми цифр шестнадцатеричного числа в таблице выше. Двоичное число 000 соответствует восьмеричной цифре 0, двоичное число 111 соответствует восьмеричной цифре 7 и т. д.

Восьмеричный	Двоичный
0	000
1	001
2	010
3	011
4	100
5	101
6	110
7	111

Преобразование восьмеричного числа в двоичное происходит так же, как и шестнадцатеричное :

65 ₈ = 110 101 ₂

17 ₈ = 001 111 ₂

И из двоичного в восьмеричный:

101100 ₂ = 101 100 ₂ сгруппировано = 54 ₈

10011 ₂ = 010 011 ₂ сгруппированы с заполнением = 23 ₈

И от восьмеричного к десятичному:

65 ₈ = (6 × 8 ¹ ) + (5 × 8 ⁰ ) = (6 × 8) + (5 × 1) = 53 ₁₀

127 ₈ = (1 × 8 ² ) + (2 × 8 ¹ ) + (7 × 8 ⁰ ) = (1 × 64) + (2 × 8) + (7 × 1) = 87 ₁₀

Представление действительных чисел

Нецелые числа могут быть представлены с помощью отрицательных степеней, которые отделяются от других цифр с помощью точки счисления (называемой десятичной точкой в ​​десятичной системе). Например, двоичное число 11.01 ₂ означает:

1 × 2 1	(1 × 2 = 2 )	плюс
1 × 2 0	(1 × 1 = 1 )	плюс
0 × 2 −1	(0 × 1 ⁄ 2 = 0 )	плюс
1 × 2 −2	(1 × 1 ⁄ 4 = 0.25 )

Всего 3,25 десятичных числа.

Все двоично-рациональные числа ${\frac {p}{2^{a}}}$ иметь завершающую двоичную цифру — двоичное представление имеет конечное число членов после точки счисления. Другие рациональные числа имеют двоичное представление, но вместо того, чтобы заканчиваться, они повторяются с конечной последовательностью цифр, повторяющейся бесконечно. Например

$${\frac {1_{10}}{3_{10}}}={\frac {1_{2}}{11_{2}}}=0.01010101{\overline {01}}\ldots \,_{2}$$ $${\frac {12_{10}}{17_{10}}}={\frac {1100_{2}}{10001_{2}}}=0.1011010010110100{\overline {10110100}}\ldots \,_{2}$$

Явление, заключающееся в том, что двоичное представление любого рационального числа либо завершается, либо повторяется, также встречается в других системах счисления, основанных на системе счисления. См., например, объяснение в десятичном формате . Еще одним сходством является существование альтернативных представлений для любого завершающего представления, основанное на том факте, что 0,111111... является суммой геометрической прогрессии 2. ⁻¹ + 2 ⁻² + 2 ⁻³ + ... что равно 1.

Двоичные числа, которые не заканчиваются и не повторяются, представляют собой иррациональные числа . Например,

• 0.10100100010000100000100... имеет шаблон, но это не повторяющийся шаблон фиксированной длины, поэтому число иррационально.
• 1.0110101000001001111001100110011111110... - это двоичное представление ${\sqrt {2}}$, квадратный корень из 2 , еще одно иррациональное явление. Он не имеет четко выраженной закономерности.

См. также

• ASCII
• Сбалансированный тройной
• Побитовая операция
• Двоичный код
• Двоично-десятичный код
• Палец двоичный
• Код Грея
• ИЭЭЭ 754
• Регистр сдвига с линейной обратной связью
• Смещенный двоичный файл
• Кибинарий
• Сокращение слагаемых
• Избыточное двоичное представление
• Повторяющаяся десятичная дробь
• Дополнение до двух
• Юникод

Внешние ссылки

• Двоичная система в самом разгаре
• Преобразование дробей в кратчайшие сроки
• Система двубуквенного шифрования сэра Фрэнсиса Бэкона. Архивировано 23 сентября 2016 года в Wayback Machine и предшествует двоичной системе счисления.