Двоичное число - Binary number

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

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

История

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

Египет

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

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

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

Китай

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

I Ching датируется до н.э. 9 -го века в Китае. Двоичная нотация в И-Цзин используется для интерпретации его техники четвертичного предсказания .

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

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

Индия

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

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

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

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

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

В конце 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 0 1 0 числовое значение 2 1
0 1 0 0 числовое значение 2 2
1 0 0 0 числовое значение 2 3

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

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

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

Более поздние разработки

Джордж Буль

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

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

В ноябре 1937 года Джордж Стибиц , тогда работавший в Bell Labs , завершил построенный на основе реле компьютер, который он назвал «Модель K» (от « K itchen», где он его собрал), который рассчитывал с использованием двоичного сложения. Bell Labs санкционировала полную исследовательскую программу в конце 1938 года под руководством Стибица. Их компьютер комплексных чисел, завершенный 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 (нижний индекс, обозначающий двоичное представление с основанием 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 0 , следующая представляет 2 1 , затем 2 2 и так далее. Значение двоичного числа - это сумма степеней двойки, представленная каждой цифрой «1». Например, двоичное число 100101 преобразуется в десятичную форму следующим образом:

100101 2 = [( 1 ) × 2 5 ] + [( 0 ) × 2 4 ] + [( 0 ) × 2 3 ] + [( 1 ) × 2 2 ] + [( 0 ) × 2 1 ] + [( 1 ) × 2 0 ]
100101 2 = [ 1 × 32] + [ 0 × 16] + [ 0 × 8] + [ 1 × 4] + [ 0 × 2] + [ 1 × 1]
100101 2 = 37 10

Фракции

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

Дробная часть Десятичный Двоичный Дробное приближение
1/1 1  или  0,999 ... 1  или  0,111 ... 1/2 + 1/4 + 1/8 ...
1/2 0,5  или  0,4999 ... 0,1  или  0,0111 ... 1/4 + 1/8 + 1/16. . .
1/3 0,333 ... 0,010101 ... 1/4 + 1/16 + 1/64. . .
1/4 0,25  или  0,24999 ... 0,01  или  0,00111 ... 1/8 + 1/16 + 1/32. . .
1/5 0,2  или  0,1999 ... 0,00110011 ... 1/8 + 1/16 + 1/128. . .
1/6 0,1666 ... 0,0010101 ... 1/8 + 1/32 + 1/128. . .
1/7 0,142857142857 ... 0,001001 ... 1/8 + 1/64 + 1/512. . .
1/8 0,125  или  0,124999 ... 0,001  или  0,000111 ... 1/16 + 1/32 + 1/64. . .
1/9 0,111 ... 0,000111000111 ... 1/16 + 1/32 + 1/64. . .
1/10 0,1  или  0,0999 ... 0,000110011 ... 1/16 + 1/32 + 1/256. . .
1/11 0,090909 ... 0,00010111010001011101 ... 1/16 + 1/64 + 1/128. . .
1/12 0,08333 ... 0,00010101 ... 1/16 + 1/64 + 1/256. . .
1/13 0,076923076923 ... 0,000100111011000100111011 ... 1/16 + 1/128 + 1/256. . .
1/14 0,0714285714285 ... 0,0001001001 ... 1/16 + 1/128 + 1/1024. . .
1/15 0,0666 ... 0,00010001 ... 1/16 + 1/256. . .
1/16 0,0625  или  0,0624999 ... 0,0001  или  0,0000111 ... 1/32 + 1/64 + 1/128. . .

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

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

Добавление

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

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

0 + 0 → 0
0 + 1 → 1
1 + 0 → 1
1 + 1 → 0, перенесем 1 (так как 1 + 1 = 2 = 0 + (1 × 2 1 ))

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

5 + 5 → 0, перенесем 1 (так как 5 + 5 = 10 = 0 + (1 × 10 1 ))
7 + 9 → 6, перенесем 1 (так как 7 + 9 = 16 = 6 + (1 × 10 1 ))

Это называется переноской . Когда результат сложения превышает значение цифры, процедура состоит в том, чтобы «перенести» избыточную сумму, разделенную на основание системы счисления (то есть 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 2 (13 10 ) и 10111 2 (23 10 ). В верхнем ряду показаны использованные биты переноса. Начиная с крайнего правого столбца, 1 + 1 = 10 2 . 1 переносится влево, а 0 пишется внизу самого правого столбца. Добавляется второй столбец справа: снова 1 + 0 + 1 = 10 2 ; переносится 1, а внизу пишется 0. Третий столбец: 1 + 1 + 1 = 11 2 . На этот раз переносится 1, а в нижнем ряду написано 1. В результате получается окончательный ответ 100100 2 (36 десятичных знаков).

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

Метод длительного ношения

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

     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 2 (958 10 ) и 1 0 1 0 1 1 0 0 1 1 2 (691 10 ), используя традиционный метод переноса на слева и длинный способ переноски справа:

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 2 (1649 10 ). В нашем простом примере с использованием малых чисел традиционный метод переноса требовал восьми операций переноса, тогда как метод длительного переноса требовал только двух, что означает существенное сокращение усилий.

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

0 1
0 0 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

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

A - B = A + не B + 1

Умножение

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

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

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

Например, двоичные числа 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

Бинарная таблица умножения совпадает с таблицей истинности в логической конъюнкции операции .

Разделение

Длинное деление в двоичном формате снова похоже на его десятичный аналог.

В приведенном ниже примере делитель равен 101 2 , или 5 в десятичной системе, а делимое - 11011 2 или 27 в десятичной системе. Процедура такая же, как и для десятичного деления в столбик ; здесь делитель 101 2 переходит в первые три цифры 110 2 делимого один раз, поэтому в верхней строке пишется «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 2 составляет 101 2 , как показано в верхней строке, а остаток, показанный в нижней строке, равен 10 2 . В десятичном выражении это соответствует тому факту, что 27 разделить на 5 равно 5, а остаток - 2.

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

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

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

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

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

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

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

Десятичный

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

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

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

Приоритетное значение × 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 10 . Первое предшествующее значение 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 2 , первая цифра равна , вторая и т. Д. Таким образом, если на первом месте после десятичной дроби стоит 1, то это число не меньше , и наоборот. Удвоение этого числа равно как минимум 1. Это предлагает алгоритм: многократно удваивайте число, которое нужно преобразовать, записывайте, если результат равен как минимум 1, а затем отбрасывайте целую часть.

Например, 10 в двоичном формате:

Преобразование Результат
0.
0,0
0,01
0,010
0,0101

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

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

Преобразование Результат
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 .... Может показаться неожиданным, что завершающие десятичные дроби могут иметь повторяющиеся расширения в двоичном формате. Именно по этой причине многие с удивлением обнаруживают, что 0,1 + ... + 0,1 (10 сложений) отличается от 1 в арифметике с плавающей запятой . Фактически, единственные двоичные дроби с завершающимися расширениями имеют форму целого числа, деленного на степень 2, а 1/10 - нет.

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

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

Для очень больших чисел эти простые методы неэффективны, потому что они выполняют большое количество умножений или делений, когда один операнд очень велик. Простой алгоритм «разделяй и властвуй» более эффективен асимптотически: для данного двоичного числа оно делится на 10 k , где k выбирается так, чтобы частное примерно равнялось остатку; затем каждая из этих частей преобразуется в десятичную форму и объединяется . Учитывая десятичное число, его можно разделить на две части примерно одинакового размера, каждая из которых преобразуется в двоичную, после чего первая преобразованная часть умножается на 10 k и добавляется ко второй преобразованной части, где 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
C шестнадцатеричный знак равно 12 дек знак равно 14 окт 1 1 0 0
D шестнадцатеричный знак равно 13 дек знак равно 15 окт 1 1 0 1
E шестнадцатеричный знак равно 14 дек знак равно 16 окт 1 1 1 0
F шестнадцатеричный знак равно 15 дек знак равно 17 окт 1 1 1 1

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

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

3A 16 = 0011 1010 2
E7 16 = 1110 0111 2

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

1010010 2 = 0101 0010 сгруппировано с заполнением = 52 16
11011101 2 = 1101 1101 сгруппировано = DD 16

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

C0E7 16 = (12 × 16 3 ) + (0 × 16 2 ) + (14 × 16 1 ) + (7 × 16 0 ) = (12 × 4096) + (0 × 256) + (14 × 16) + ( 7 × 1) = 49 383 10

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

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

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

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

65 8 = 110 101 2
17 8 = 001 111 2

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

101100 2 = 101 100 2 Сгруппированные = 54 8
10011 2 = 010 011 2 сгруппированы с заполнением = 23 8

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

65 8 = (6 × 8 1 ) + (5 × 8 0 ) = (6 × 8) + (5 × 1) = 53 10
127 8 = (1 × 8 2 ) + (2 × 8 1 ) + (7 × 8 0 ) = (1 × 64) + (2 × 8) + (7 × 1) = 87 10

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

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

1 × 2 1 (1 × 2 = 2 ) плюс
1 × 2 0 (1 × 1 = 1 ) плюс
0 × 2 -1 (0 × 12 = 0 ) плюс
1 × 2 −2 (1 × 14 = 0,25 )

Всего 3,25 десятичной дроби.

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

Феномен, заключающийся в том, что двоичное представление любого рационального числа либо завершается, либо повторяется, также встречается в других системах счисления, основанных на системе счисления. См., Например, объяснение в десятичном формате . Другое сходство заключается в существовании альтернативных представлений для любого завершающего представления, основанного на том факте, что 0,111111 ... является суммой геометрического ряда 2 −1 + 2 −2 + 2 −3 + ..., который равен 1.

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

  • 0.10100100010000100000100 ... имеет шаблон, но это не повторяющийся шаблон фиксированной длины, поэтому число иррационально
  • 1.0110101000001001111001100110011111110 ... это двоичное представление , квадратный корень из 2 , еще одно иррациональное. У него нет заметного рисунка.

Смотрите также

использованная литература

дальнейшее чтение

  • Санчес, Хулио; Кантон, Мария П. (2007). Программирование микроконтроллера: микросхема PIC . Бока-Ратон, Флорида: CRC Press. п. 37. ISBN 978-0-8493-7189-9.
  • Редмонд, Джеффри; Хон, Цзы-Ки (2014). Обучение И-Цзин . Издательство Оксфордского университета. ISBN 978-0-19-976681-9.

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