stringtranslate.com

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

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

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

История

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

Египет

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

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

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

Китай

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

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

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

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

Классическая античность

Этруски разделили внешний край гадательных печеней на шестнадцать частей, на каждой из которых было написано имя божества и его область неба. Каждая область печени производила бинарное чтение, которое объединялось в окончательный бинарник для гадания. [10]

Гадание в древнегреческом оракуле Додона работало путем вытягивания из отдельных банок, вопросительных табличек и шариков «да» и «нет». Затем результат объединялся, чтобы составить окончательное пророчество. [11]

Индия

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

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

Африка

Ифа — африканская система гадания . Похожа на И Цзин , но имеет до 256 бинарных знаков, [ 17] в отличие от И Цзин , в котором их 64. Ифа возникла в 15 веке в Западной Африке среди народа йоруба . В 2008 году ЮНЕСКО добавила Ифа в свой список « Шедевров устного и нематериального наследия человечества ». [18] [19]

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

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

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

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

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

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

Лейбниц

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

Лейбниц написал более сотни рукописей о двоичной системе, большинство из которых остались неопубликованными. [26] До его первой специальной работы в 1679 году многочисленные рукописи содержат ранние попытки исследовать двоичные концепции, включая таблицы чисел и основные вычисления, часто набросанные на полях работ, не связанных с математикой. [26]

Его первая известная работа о двоичной системе, «О двоичной прогрессии» , была написана в 1679 году. Лейбниц ввел преобразование между десятичной и двоичной системой счисления, а также алгоритмы для выполнения основных арифметических операций, таких как сложение, вычитание, умножение и деление с использованием двоичных чисел. Он также разработал форму двоичной алгебры для вычисления квадрата шестизначного числа и извлечения квадратных корней. [26]

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

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

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

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

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

—  Письмо Лейбница герцогу Брауншвейгскому с приложением гексаграмм И Цзин [31]

Дальнейшие события

Джордж Буль

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

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

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

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

Представление

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

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

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

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

При произнесении двоичные числа обычно читаются цифра за цифрой, чтобы отличать их от десятичных чисел. Например, двоичное число 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, причем самый правый бит представляет собой 2 0 , следующий представляет собой 2 1 , затем 2 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 × 1/10 не будет точно равняться 1 в двоичной арифметике с плавающей точкой . Например, чтобы интерпретировать двоичное выражение для 1/3 = .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 10 ).

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

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

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

 Двоично-десятичный 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

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

А − В = А + не В + 1

Умножение

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

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

Например, двоичные числа 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 ----- 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 могут быть выполнены над соответствующими битами в двух двоичных числах, предоставленных в качестве входных данных. Логическая операция NOT может быть выполнена над отдельными битами в одном двоичном числе, предоставленном в качестве входных данных. Иногда такие операции могут использоваться в качестве арифметических сокращений и могут иметь и другие вычислительные преимущества. Например, арифметический сдвиг влево двоичного числа эквивалентен умножению на (положительную, целую) степень числа 2.

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

Десятичная система счисления в двоичную

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

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

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

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

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

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

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

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

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

Или, например, 0,1 10 в двоичной системе счисления будет:

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

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

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

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

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

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

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

3А 16 = 0011 1010 2
Е7 16 = 1110 0111 2

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

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.

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

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

Ссылки

  1. ^ "3.3. Двоичный код и его преимущества — CS160 Reader". computerscience.chemeketa.edu . Получено 22 мая 2024 г. .
  2. ^ Робсон, Элеанор ; Стедалл, Жаклин , ред. (2009), «Миф № 2: дроби глаза Гора», Оксфордский справочник по истории математики, Oxford University Press, стр. 790, ISBN 9780199213122
  3. ^ Крисомалис, Стивен (2010), Числовая нотация: сравнительная история, Cambridge University Press, стр. 42–43, ISBN 9780521878180.
  4. ^ Рудман, Питер Штром (2007), Как возникла математика: первые 50 000 лет, Prometheus Books, стр. 135–136, ISBN 9781615921768.
  5. ^ ab Эдвард Хакер; Стив Мур; Лоррейн Патско (2002). И Цзин: Аннотированная библиография. Routledge. стр. 13. ISBN 978-0-415-93969-0.
  6. ^ ab Redmond, Geoffrey; Hon, Tze-Ki (2014). Обучение И-Цзин . Oxford University Press. стр. 227. ISBN 978-0-19-976681-9.
  7. ^ ab Jonathan Shectman (2003). Новаторские научные эксперименты, изобретения и открытия XVIII века. Greenwood Publishing. стр. 29. ISBN 978-0-313-32015-6.
  8. ^ Маршалл, Стив. "Последовательности гексаграмм Ицзин: квадрат Шао Юн (последовательность Фуси)" . Получено 15 сентября 2022 г. Можно сказать, что [двоичная последовательность Фуси] — это более разумный способ представления гексаграммы в виде двоичных чисел... Рассуждения, если таковые имеются, которые информируют о последовательности [царя Вэня], неизвестны.
  9. ^ Чжунлянь, Ши; Вэньчжао, Ли; Позер, Ганс (2000). Бинарная система Лейбница и «Сяньтянь Ту» Шао Юна в: Das Neueste über China: GW Leibnizens Novissima Sinica von 1697: Internationales Symposium, Берлин, 4-7 октября 1997 г. Штутгарт: Franz Steiner Verlag. стр. 165–170. ISBN 3515074481.
  10. ^ Коллинз, Дерек (2008). «Картирование внутренностей: практика греческой гепатоскопии». Американский журнал филологии . 129 (3): 319–345. ISSN  0002-9475. JSTOR  27566714.
  11. ^ Джонстон, Сара Айлс (2008). Древнегреческое гадание . Древние религии Блэквелла (1-е изд.). Молден, Массачусетс: Wiley-Blackwell. ISBN 978-1-4051-1573-5.
  12. ^ Санчес, Хулио; Кантон, Мария П. (2007). Программирование микроконтроллера: микрочип PIC . Бока-Ратон, Флорида: CRC Press. стр. 37. ISBN 978-0-8493-7189-9.
  13. ^ WS Anglin и J. Lambek, Наследие Фалеса , Springer, 1995, ISBN 0-387-94544-X 
  14. ↑ Математика для поэтов и барабанщиков. Архивировано 16 июня 2012 г. на Wayback Machine (pdf, 145 КБ)
  15. ^ Стахов, Алексей ; Олсен, Скотт Энтони (2009). Математика гармонии: от Евклида до современной математики и компьютерной науки. World Scientific. ISBN 978-981-277-582-5.
  16. ^ Б. ван Нутен, «Двоичные числа в индийской древности», Журнал индийских исследований, том 21, 1993, стр. 31–50
  17. ^ Ландри, Тимоти Р. (2019). Vodún: secrecy and the search for divine power . Contemporary ethnography (1st ed.). Филадельфия: University of Pennsylvania Press. стр. 25. ISBN 978-0-8122-5074-9.
  18. ^ Ландри 2019, стр. 154.
  19. ^ "Система гадания Ифа" . Получено 5 июля 2017 г.
  20. ^ Бендер, Андреа; Беллер, Сигхард (16 декабря 2013 г.). «Изобретение Мангареваном двоичных шагов для упрощения вычислений». Труды Национальной академии наук . 111 (4): 1322–1327. doi : 10.1073/pnas.1309160110 . PMC 3910603. PMID  24344278 . 
  21. ^ Боуэрн, Клэр; Зенц, Джейсон (2012). «Разнообразие в системах счисления австралийских языков». Anthropological Linguistics . 54 (2): 133–160. ISSN  0003-5483. JSTOR  23621076.
  22. ^ (см. Bonner 2007 [1] Архивировано 3 апреля 2014 года на Wayback Machine , Fidora et al. 2011 [2] Архивировано 8 апреля 2019 года на Wayback Machine )
  23. ^ ab Бэкон, Фрэнсис (1605). «Прогресс обучения». Лондон. стр. Глава 1.
  24. ^ Ширли, Джон У. (1951). «Двоичная система счисления до Лейбница». American Journal of Physics . 19 (8): 452–454. Bibcode : 1951AmJPh..19..452S. doi : 10.1119/1.1933042.
  25. ^ Инейхен, Р. (2008). «Лейбниц, Карамуэль, Харриот и дуальная система» (PDF) . Mitteilungen der deutschen Mathematiker-Vereinigung (на немецком языке). 16 (1): 12–15. дои : 10.1515/dmvm-2008-0009. S2CID  179000299.
  26. ^ abc Стрикленд, Ллойд (2020), Шрираман, Бхарат (ред.), «Лейбниц о числовых системах», Справочник по истории и философии математической практики , Cham: Springer International Publishing, стр. 1–31, doi :10.1007/978-3-030-19071-2_90-1, ISBN 978-3-030-19071-2, получено 20 августа 2024 г.
  27. ^ ab Лейбниц Г., Explication de l'Arithmétique Binaire, Die Mathematische Schriften, изд. К. Герхардт, Берлин, 1879 г., т.7, стр.223; англ. перевод [3]
  28. ^ «Буве и Лейбниц: научная переписка», Свидерски 1980
  29. ^ Лейбниц: «Китайцы утратили значение Cova или Lineations Фуси, возможно, более тысячи лет назад, и они написали комментарии по этому вопросу, в которых они искали не знаю какие далекие значения, так что их истинное объяснение теперь должно исходить от европейцев. Вот как: Это было чуть больше двух лет назад, когда я послал преподобному отцу Буве, 3 знаменитому французскому иезуиту, который живет в Пекине, мой метод счета с помощью 0 и 1, и ничего больше не требовалось, чтобы заставить его признать, что это был ключ к числам Фуси. Написав мне 14 ноября 1701 года, он прислал мне эту великую цифру философского принца, которая доходит до 64 и не оставляет никаких дальнейших оснований для сомнений в истинности нашей интерпретации, так что можно сказать, что этот отец расшифровал загадку Фуси с помощью того, что я ему сообщил. И поскольку эти числа являются, возможно, самым древним памятником [GM VII, p227] науки, который существует в мир, это восстановление их смысла после столь большого промежутка времени, покажется еще более любопытным».
  30. ^ Эйтон, Эрик Дж. (1985). Лейбниц: Биография . Тейлор и Фрэнсис. стр. 245–8. ISBN 0-85274-470-6.
  31. ^ ab JEH Smith (2008). Лейбниц: Какой тип рационалиста?: Какой тип рационалиста?. Springer. стр. 415. ISBN 978-1-4020-8668-7.
  32. ^ Юэн-Тин Лай (1998). Лейбниц, Мистицизм и религия. Springer. С. 149–150. ISBN 978-0-7923-5223-5.
  33. ^ Буль, Джордж (2009) [1854]. Исследование законов мышления, на которых основаны математические теории логики и вероятностей (Macmillan, Dover Publications, переиздано с исправлениями [1958] ред.). Нью-Йорк: Cambridge University Press. ISBN 978-1-108-00153-3.
  34. ^ Шеннон, Клод Элвуд (1940). Символический анализ релейных и коммутационных схем (диссертация). Кембридж: Массачусетский технологический институт. hdl :1721.1/11173.
  35. ^ "Национальный зал славы изобретателей – Джордж Р. Стибиц". 20 августа 2008 г. Архивировано из оригинала 9 июля 2010 г. Получено 5 июля 2010 г.
  36. ^ "George Stibitz: Bio". Кафедра математики и компьютерных наук, Университет Денисон. 30 апреля 2004 г. Получено 5 июля 2010 г.
  37. ^ «Пионеры – люди и идеи, которые изменили мир – Джордж Стибиц (1904–1995)». Керри Редшоу. 20 февраля 2006 г. Получено 5 июля 2010 г.
  38. ^ "George Robert Stibitz – Obituary". Computer History Association of California. 6 февраля 1995 г. Получено 5 июля 2010 г.
  39. ^ Рохас, Рауль (апрель–июнь 1997 г.). «Наследие Конрада Цузе: архитектура Z1 и Z3» (PDF) . IEEE Annals of the History of Computing . 19 (2): 5–16. doi :10.1109/85.586067. Архивировано (PDF) из оригинала 3 июля 2022 г. . Получено 3 июля 2022 г. .(12 страниц)
  40. ^ "Введение в двоичную систему – Пересмотр 1 – GCSE Computer Science". BBC . Получено 26 июня 2019 г.
  41. ^ аб Кювелер, Герд; Швох, Дитрих (2013) [1996]. Arbeitsbuch Informatik – eine praxisorientierte Einführung in die Datenverarbeitung mit Projektaufgabe (на немецком языке). Vieweg-Verlag, перепечатка: Springer-Verlag. дои : 10.1007/978-3-322-92907-5. ISBN 978-3-528-04952-2. 9783322929075.
  42. ^ аб Кювелер, Герд; Швох, Дитрих (4 октября 2007 г.). Informatik für Ingenieure und Naturwissenschaftler: PC- und Mikrocomputertechnik, Rechnernetze (на немецком языке). Том. 2 (5-е изд.). Просмотр, перепечатка: Springer-Verlag. ISBN 978-3834891914. 9783834891914.
  43. ^ "Base System". Архивировано из оригинала 23 октября 2017 года . Получено 31 августа 2016 года .

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

В Wikibooks есть книга по теме: Фракталы/Математика/двоичные числа
На Викискладе есть медиафайлы по теме Двоичная система счисления .