Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

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

История [ править ]

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

Египет [ править ]

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

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

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

Китай [ править ]

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

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

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

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

Индия [ править ]

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

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

Другие культуры [ править ]

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

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

В конце 13 века Рамон Луллий стремился объяснить всю мудрость во всех отраслях человеческого знания того времени. Для этой цели он разработал общий метод или Ars generalis, основанный на бинарных комбинациях ряда простых базовых принципов или категорий, в связи с чем его считали предшественником компьютерной науки и искусственного интеллекта. [15]

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

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

Лейбниц и И Цзин [ править ]

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

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

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

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

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

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

Более поздние разработки [ править ]

Джордж Буль

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

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

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

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

Представление [ править ]

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

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

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

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

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

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

Подсчет в двоичном формате [ править ]

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

Десятичный счет [ править ]

Для десятичного счета используются десять символов от 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 чередуются навсегда.

Двоичная арифметика [ править ]

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

Дополнение [ править ]

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

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

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 (переносимые цифры) 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 9 приведет к числу 1, за которым следует строка из n 0:

 Двоичный десятичный 1 1 1 1 1 аналогично 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 ), используя традиционный метод переноса на слева и длинный способ переноски справа:

Традиционный метод ношения Метод длительного ношения против. 1 1 1 1 1 1 1 1 (переносимые цифры) 1 ← 1 ← переносить 1 до тех пор, пока она не окажется на одну цифру после «строки» ниже 1 1 1 0 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 0 зачеркнуть «строку»,+ 1 0 1 0 1 1 0 0 1 1 + 1 0 1 0 1 1 0 0 1 1 и зачеркнуть цифру, которая была добавлена ​​к ней—————————————————————————————————————————————= 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 - 0 → 0
0-1 → 1, заимствовать 1
1-0 → 1
1-1 → 0

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

 * * * * (столбцы, отмеченные звездочкой, заимствованы из) 1 1 0 1 1 1 0- 1 0 1 1 1----------------= 1 0 1 0 1 1 1
 * (столбцы, отмеченные звездочкой, заимствованы из) 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 ( А ) × 1 0 1 0 ( В ) --------- 0 0 0 0 ← Соответствует крайнему правому нулю в B + 1 0 1 1 ← Соответствует следующей единице в 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 в десятичной системе) × 1 1 0. 0 1 B (6,25 в десятичной системе) ------------------- 1. 0 1 1 0 1 ← Соответствует единице в B + 0 0. 0 0 0 0 ← Соответствует нулю в 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 в десятичной системе)

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

Таблица умножения [ править ]

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

Подразделение [ править ]

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

В приведенном ниже примере делитель равен 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 ----- 1 0

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

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

Квадратный корень [ править ]

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

 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. [34]

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

Результат - 1197 10 . Первое предшествующее значение 0 - это просто начальное десятичное значение. Этот метод представляет собой применение схемы Хорнера .

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

В дробном двоичном числе, таком как 0,11010110101 2 , первая цифра равна , вторая и т. Д. Таким образом, если на первом месте после десятичной дроби стоит 1, то число не меньше , и наоборот. Удвоение этого числа равно как минимум 1. Это предлагает алгоритм: многократно удваивайте число, которое нужно преобразовать, записывайте, если результат равен как минимум 1, а затем отбрасывайте целую часть.

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

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

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

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

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

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

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

Шестнадцатеричный [ править ]

Двоичное число может быть легче преобразовано в шестнадцатеричное и обратно. Это потому, что основание системы счисления шестнадцатеричной системы (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 и так далее.

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

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 означает:

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

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

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

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

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

См. Также [ править ]

  • Сбалансированный тройной
  • Бинарный код
  • Десятичное число с двоичным кодом
  • Бинарный палец
  • Код Грея
  • IEEE 754
  • Регистр сдвига с линейной обратной связью
  • Смещение двоичное
  • Quibinary
  • Сокращение слагаемых
  • Избыточное двоичное представление
  • Повторяющаяся десятичная дробь
  • Два дополнения

Ссылки [ править ]

  1. ^ Робсон, Элеонора ; Стедалл, Жаклин , ред. (2009), «Миф № 2: фракции глаза Гора», Оксфордский справочник по истории математики , Oxford University Press, стр. 790, ISBN 9780199213122
  2. ^ Chrisomalis, Стивен (2010), Числовое обозначение: сравнительная история , Cambridge University Press, стр. 42–43, ISBN 9780521878180.
  3. ^ Rudman, Питер Стром (2007), как математика Happened: Первая 50000 лет , Prometheus Books, стр 135-136,. ISBN 9781615921768.
  4. ^ а б Эдвард Хакер; Стив Мур; Лоррейн Пацко (2002). И Цзин: аннотированная библиография . Рутледж. п. 13. ISBN 978-0-415-93969-0.
  5. ^ a b Redmond & Hon (2014) , стр. 227.
  6. ^ a b Джонатан Шектман (2003). Новаторские научные эксперименты, изобретения и открытия 18 века . Издательство "Гринвуд". п. 29. ISBN 978-0-313-32015-6.
  7. ^ Чжунлянь, Ши; Вэньчжао, Ли; Позер, Ганс (2000). Бинарная система Лейбница и "Xiantian Tu in" Шао Юна : Das Neueste über China: GW Leibnizens Novissima Sinica von 1697: Internationales Symposium, Берлин 4. бис 7. Октябрь 1997 г.. Штутгарт: Франц Штайнер Верлаг. С. 165–170. ISBN 3515074481.
  8. ^ Санчес, Хулио; Кантон, Мария П. (2007). Программирование микроконтроллера: микрочип PIC . Бока-Ратон, Флорида: CRC Press. п. 37. ISBN 978-0-8493-7189-9.
  9. WS Anglin и J. Lambek, The Heritage of Thales , Springer, 1995, ISBN 0-387-94544-X 
  10. ^ Б Двоичные числа в Древней Индии
  11. ^ Математика для поэтов и барабанщиков. Архивировано 16 июня 2012 года в Wayback Machine (pdf, 145 КБ)
  12. ^ Стахов Алексей ; Олсен, Скотт Энтони (2009). Математика гармонии: от Евклида до современной математики и информатики . ISBN 978-981-277-582-5.
  13. ^ Б. ван Nooten, «Двоичные числа в индийской древности», журнал индийских исследований, том 21, 1993, стр. 31-50
  14. ^ Бендер, Андреа; Беллер, Зигард (16 декабря 2013 г.). «Мангареванское изобретение двоичных шагов для облегчения вычислений» . Труды Национальной академии наук . 111 (4): 1322–1327. DOI : 10.1073 / pnas.1309160110 . PMC 3910603 . PMID 24344278 .  
  15. ^ (см. Bonner 2007 [1] Архивировано 3 апреля 2014 года в Wayback Machine , Fidora et al. 2011 [2] )
  16. ^ a b Бэкон, Фрэнсис (1605). «Развитие обучения» . Лондон. С. Глава 1.
  17. ^ Ширли, Джон В. (1951). «Двоичное счисление перед Лейбницем». Американский журнал физики . 19 (8): 452–454. Bibcode : 1951AmJPh..19..452S . DOI : 10.1119 / 1.1933042 .
  18. ^ Ineichen, R. (2008). "Лейбниц, Карамуэль, Харриот и дас Dualsystem" (PDF) . Mitteilungen der deutschen Mathematiker-Vereinigung (на немецком языке). 16 (1): 12–15. DOI : 10,1515 / dmvm-2008-0009 . S2CID 179000299 .  
  19. ^ a b Лейбниц Г., Explication de l'Arithmétique Binaire, Die Mathematische Schriften, изд. К. Герхард, Берлин 1879, т. 7, стр. 223; Англ. перевод [3]
  20. ^ a b c Дж. Э. Х. Смит (2008). Лейбниц: Какой рационалист ?: Какой рационалист? . Springer. п. 415. ISBN 978-1-4020-8668-7.
  21. Перейти ↑ Aiton, Eric J. (1985). Лейбниц: Биография . Тейлор и Фрэнсис. С. 245–8. ISBN 0-85274-470-6.
  22. Yuen-Ting Lai (1998). Лейбниц, мистицизм и религия . Springer. С. 149–150. ISBN 978-0-7923-5223-5.
  23. ^ Буль, Джордж (2009) [1854]. Исследование законов мысли, на которых основаны математические теории логики и вероятностей (Macmillan, Dover Publications, переиздано с исправлениями [1958], изд.). Нью-Йорк: Издательство Кембриджского университета. ISBN 978-1-108-00153-3.
  24. ^ Шеннон, Клод Элвуд (1940). Символьный анализ релейных и коммутационных схем . Кембридж: Массачусетский технологический институт. hdl : 1721,1 / 11173 .
  25. ^ "Национальный зал славы изобретателей - Джордж Р. Стибиц" . 20 августа 2008. Архивировано из оригинала 9 июля 2010 года . Проверено 5 июля 2010 года .
  26. ^ "Джордж Стибиц: Био" . Департамент математики и компьютерных наук, Университет Денисон. 30 апреля 2004 . Проверено 5 июля 2010 года .
  27. ^ «Пионеры - люди и идеи, которые имели значение - Джордж Стибиц (1904–1995)» . Керри Редшоу. 20 февраля 2006 . Проверено 5 июля 2010 года .
  28. ^ "Джордж Роберт Стибиц - Некролог" . Калифорнийская ассоциация компьютерной истории. 6 февраля 1995 . Проверено 5 июля 2010 года .
  29. ^ Рохас, Р. (1997). "Наследие Конрада Цузе: Архитектура Z1 и Z3" (PDF) . IEEE Annals of the History of Computing . 19 (2): 5–15. DOI : 10.1109 / 85.586067 .
  30. ^ «Введение в двоичный код - Версия 1 - Компьютерные науки GCSE» . BBC . Проверено 26 июня 2019 .
  31. ^ a b Кювелер, Герд; Швох, Дитрих (2013) [1996]. Arbeitsbuch Informatik - eine praxisorientierte Einführung in die Datenverarbeitung mit Projektaufgabe (на немецком языке). Vieweg-Verlag, перепечатка: Springer-Verlag. DOI : 10.1007 / 978-3-322-92907-5 . ISBN 978-3-528-04952-2. 9783322929075.
  32. ^ a b Кювелер, Герд; Швох, Дитрих (4 октября 2007 г.). Informatik für Ingenieure und Naturwissenschaftler: PC- und Mikrocomputertechnik, Rechnernetze (на немецком языке). 2 (5-е изд.). Vieweg, перепечатка: Springer-Verlag. ISBN 978-3834891914. 9783834891914.
  33. ^ "Окончательное руководство по высшей математике по делению в столбик и его вариантам - для целых чисел" . Математическое хранилище . 24 февраля 2019 . Проверено 26 июня 2019 .
  34. ^ «Базовая система» . Проверено 31 августа 2016 года .

Дальнейшее чтение [ править ]

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

Внешние ссылки [ править ]

  • Бинарная система на пороге
  • Преобразование дробей при разрубании узла
  • Система BiLiteral Cypher сэра Фрэнсиса Бэкона предшествовала двоичной системе счисления.