Как сделать конъюнкцию двоичных чисел
Обновлено: 03.07.2024
Сайт учителя информатики. Технологические карты уроков, Подготовка к ОГЭ и ЕГЭ, полезный материал и многое другое.
Информатика. 10 класса. Босова Л.Л. Оглавление
§ 20. Преобразование логических выражений
Способ определения истинности логического выражения путём построения его таблицы истинности становится неудобным при увеличении количества логических переменных, т. к. за счёт существенного увеличения числа строк таблицы становятся громоздкими. В таких случаях выполняются преобразования логических выражений в равносильные. Для этого используют свойства логических операций, которые иначе называют законами алгебры логики.
20.1. Основные законы алгебры логики.
Приведём основные законы алгебры логики.
1. Переместительные (коммутативные) законы:
2. Сочетательные (ассоциативные) законы:
(A v В) v С = A v (В v С).
3. Распределительные (дистрибутивные) законы:
A v (В & С) = (A v В) & (A v С).
4. Законы идемпотентности (отсутствия степеней и коэффициентов):
5. Закон противоречия:
6. Закон исключённого третьего:
7. Закон двойного отрицания:
8. Законы работы с константами:
A v 1 = 1; A v O = A;
9. Законы де Моргана:
10. Законы поглощения:
Справедливость законов можно доказать построением таблиц истинности.
Пример 1. Упростим логическое выражение
Последовательно применим дистрибутивный закон и закон исключённого третьего:
Пример 2. Упростим логическое выражение
Аналогичные законы выполняются для операций объединения, пересечения и дополнения множеств. Например:
Пробуйте самостоятельно доказать один из этих законов с помощью кругов Эйлера.
Пример 3. На числовой прямой даны отрезки В = [2; 12] и С = [7; 18]. Каким должен быть отрезок А, чтобы предикат
становился истинным высказыванием при любых значениях х.
Преобразуем исходное выражение, избавившись от импликации:
причём это минимально возможное множество А.
Множество В — это отрезок [2; 12].
Изобразим это графически:
Пересечением этих множеств будет служить промежуток [2; 7[. В качестве ответа мы можем взять этот промежуток, а также любой другой, его включающий.
Чему равна минимальная длина отрезка А? Укажите ещё несколько вариантов множества А.
Пример 4. Для какого наименьшего неотрицательного целого десятичного числа а выражение
тождественно истинно (т. е. принимает значение 1 при любом неотрицательном целом значении десятичной переменной х)? Здесь & — поразрядная конъюнкция двух неотрицательных целых десятичных чисел.
Прежде всего, вспомним, что представляет собой поразрядная конъюнкция двух целых десятичных чисел, например 27 и 22.
Обратите внимание на то, что если в некотором бите хотя бы одного сомножителя есть 0, то 0 есть и в этом бите результата, а 1 в результате получается только тогда, когда в соответствующих битах каждого сомножителя есть 1.
Перепишем исходное выражение в наших обозначениях:
Рассмотрим предикат М(х) = (х & 28 ? 0). В числе 28 = 111002 4-й, 3-й и 2-й биты содержат единицы, а 1-й и 0-й — нули. Следовательно, множеством истинности этого предиката являются такие числа х, у которых хотя бы один из битов с номерами 4, 3 или 2 содержит единицу. Если и 4-й, и 3-й, и 2-й биты числа х нулевые, то высказывание х & 28 ? 0 будет ложным.
Рассмотрим предикат N(x) = (х & 45 ? 0). В числе 45 = 1011012 5-й, 3-й, 2-й и 0-й биты содержат единицы, 4-й и 1-й — нули.
Следовательно, множеством истинности этого предиката являются такие числа х, у которых хотя бы один из битов с номерами 5, 3, 2 или 0 содержит единицу. Если и 5-й, и 3-й, и 2-й, и 0-й биты числа х нулевые, то высказывание х & 45 ? 0 будет ложным.
Рассмотрим предикат К(х) = (х & 17 = 0). В числе 17 = 100012 3-й, 2-й и 1-й биты содержат нули, 4-й и 0-й — единицы. Побитовая конъюнкция 17 и х будет равна нулю, если в числе х 4-й и 0-й биты будут содержать нули. Множество истинности этого предиката — все х с нулями в 4-м и 0-м битах.
По условию задачи надо, чтобы
Запишем это выражение для рассмотренных множеств истинности:
Объединением множеств М и N являются все двоичные числа, у которых хотя бы один из битов с номерами 5, 4, 3, 2, 0 содержит единицу. Пересечением этого множества с множеством К будут все двоичные числа, у которых биты с номерами 4 и 0 будут заняты нулями, т. е. такие двоичные числа, у которых хотя бы один из битов с номерами 5, 3, 2 содержит 1. Все эти числа образуют множество А.
Искомое число а должно быть таким, чтобы при любом неотрицательном целом значении переменной х: х & а ? 0, и кроме того, оно должно быть минимальным из возможных. Этим условиям удовлетворяет число 1011002. Действительно, единицы в нём стоят в тех и только в тех битах, которые нужны для выполнения условия х & а ? 0.
Итак, требуемое число 1011002 или 4410.
Приведите пример такого десятичного числа а, что для него х & а ? 0 при любом неотрицательном целом значении десятичной переменной х, но само число а не является минимально возможным.
Пример 5. Выясним, сколько решений имеет следующая система из двух уравнений:
Конъюнкция истинна тогда и только тогда, когда истинны все образующие её высказывания. Следовательно, каждая из трёх входящих в конъюнкцию импликаций должна быть равна 1.
Начнем строить дерево решений, представив на нём значения переменных х1 и х2 при которых х1 ? х2 = 1.
Продолжим строить дерево решений. Значения переменной х3 будем выбирать такими, чтобы при имеющихся х2 импликация х2 ? х3 оставалась истинной.
То же самое проделаем для переменной х4.
На дереве видно, что рассматриваемое нами уравнение имеет 5 решений — 5 разных наборов значений логических переменных x1, х2, х3, х4, при которых выполняется равенство:
Следовательно, как и первое уравнение, это уравнение имеет 5 решений. Представим их в табличной форме:
Решение исходной системы логических уравнений — это множество различных наборов значений логических переменных х1, х2, х3, х4, у1, у2, у3, у4 таких, что при подстановке каждого из них в систему оба уравнения превращаются в истинные равенства.
Начнём строить такие наборы или двоичные цепочки. Их началом может служить любой из пяти наборов — решений первого уравнения, а концом — любой из пяти наборов — решений второго уравнения. Например, на основе одного из решений первого уравнения можно построить следующие пять решений системы:
Всего мы можем построить 5 • 5 = 25 решений системы.
Вспомните, как называется теорема комбинаторики, которую мы применили для подсчёта количества решений системы.
20.2. Логические функции
Значение любого логического выражения определяется значениями входящих в него логических переменных. Тем самым логическое выражение может рассматриваться как способ задания логической функции.
Совокупность значений п аргументов удобно интерпретировать как строку нулей и единиц длины n. Существует ровно 2 n различных двоичных строк длины n. Так как на каждой такой строке некая функция может принимать значение 0 или 1, общее количество различных булевых функций от n аргументов равно
Для n = 2 существует 16 различных логических функций.
Рассмотрим их подробнее.
С увеличением числа аргументов количество логических функций резко возрастает. Так, для трёх переменных существует 256 различных логических функций! Но изучать их все нет никакой необходимости. Дело в том, что путём преобразований функция любого количества переменных может быть выражена через функции только двух переменных. Более того, можно использовать не все, а лишь некоторые логические функции двух переменных. Например:
1) F2 и F11 (конъюнкция и отрицание второго аргумента);
2) F8 и F13 (дизъюнкция и отрицание первого аргумента);
3) F9 (стрелка Пирса, отрицание дизъюнкции);
4) F15 (штрих Шеффера, отрицание конъюнкции).
Два последних примера говорят о том, что при желании всю алгебру логики можно свести к одной функции! Но чаще всего логические функции записываются в виде логического выражения через отрицание, конъюнкцию и дизъюнкцию.
20.3. Составление логического выражения по таблице истинности и его упрощение
Ранее мы выяснили, что для любого логического выражения можно составить таблицу истинности. Справедливо и обратное: для всякой таблицы истинности можно составить соответствующее ей логическое выражение.
Алгоритм составления логического выражения по таблице истинности достаточно прост. Для этого надо:
1) отметить в таблице истинности наборы переменных, при которых значение логического выражения равно единице;
2) для каждого отмеченного набора записать конъюнкцию всех переменных следующим образом: если значение некоторой переменной в этом наборе равно 1, то в конъюнкцию включаем саму переменную, в противном случае — её отрицание;
3) все полученные конъюнкции связать операциями дизъюнкции.
Пример 6. Имеется следующая таблица истинности:
После выполнения двух первых шагов алгоритма получим:
После выполнения третьего шага получаем логическое выражение:
Попробуем упростить полученное логическое выражение. Прежде всего, вынесем за скобки В — общий сомножитель, имеющийся у всех трёх слагаемых, затем — сомножитель
, а далее используем законы алгебры логики.
САМОЕ ГЛАВНОЕ
Способ определения истинности логического выражения путём построения его таблицы истинности становится неудобным при увеличении количества логических переменных, т. к. за счёт существенного увеличения числа строк таблицы становятся громоздкими. В таких случаях выполняются преобразования логических выражений в равносильные. Для этого используют свойства логических операций, которые иначе называют законами алгебры логики. Аналогичные законы имеют место и в алгебре множеств.
Логическая функция может быть задана с помощью таблицы истинности или аналитически, т. е. с помощью логического выражения.
Для всякой таблицы истинности можно составить соответствующее ей логическое выражение.
Вопросы и задания
1. Какие из рассмотренных законов алгебры логики аналогичны законам алгебры чисел, а какие нет?
2. Докажите второй закон де Моргана с помощью таблиц истинности.
3. Путём преобразования докажите равносильность следующих высказываний:
4. Упростите логические формулы:
*5. Найдите X,
6. На числовой прямой даны два отрезка: Р = [10; 25] и Q = [20; 55]. Укажите наибольшую возможную длину такого отрезка А, что выражение (х ? А) ? ((х ? Р) v (x ? Q)) истинно при любом значении переменной х.
7. Элементами множеств А, Р и Q являются натуральные числа, причём Р = и Q = .
Известно, что выражение
истинно при любом значении переменной х. Определите наименьшее возможное количество элементов множества А.
*8. На числовой прямой даны два отрезка: М = [10; 60] и N = [40; 80]. Укажите наименьшую возможную длину такого отрезка А, что выражение
истинно при любом значении переменной х.
9. Для какого наименьшего неотрицательного целого десятичного числа А формула x & 25 ? 0 ? (x & 17 = 0 ? (x & А ? 0) тождественно истинна, т. е. принимает значение 1 при любом неотрицательном целом значении десятичной переменной х? (Здесь & — поразрядная конъюнкция двух неотрицательных целых десятичных чисел.)
*10. Определите наибольшее натуральное десятичное число А, при котором выражение ((x & 46 = 0) v (х & 18 = 0)) ? ((х & 115 ? 0) v (х & А = 0)) тождественно истинно, т. е. принимает значение 1 при любом натуральном значении десятичной переменной х. (Здесь & — поразрядная конъюнкция двух неотрицательных целых десятичных чисел.)
11. Сколько различных решений имеет система уравнений:
12. Сколько существует различных логических функций от четырёх переменных?
13. По заданной таблице истинности составьте логические выражения для функций F1, F2.
14. По известным таблицам истинности запишите аналитическое представление импликации, эквиваленции и строгой дизъюнкции.
15. Логические функции штрих Шеффера и стрелка Пирса названы так в честь математиков, исследовавших их свойства. Подготовьте краткую биографическую справку об одном из этих учёных.
16. По заданной таблице истинности составьте логические выражения для функций F1, F2.
17. Запишите логическое выражение для логической функции F(A, В, С), равной 1 на наборах 011, 101, 110, 111. Попытайтесь упростить полученное выражение.
В этой статье я расскажу вам о том, как работают битовые операции. С первого взгляда они могут показаться вам чем-то сложным и бесполезным, но на самом деле это совсем не так. В этом я и попытаюсь вас убедить.
Введение
Побитовые операторы проводят операции непосредственно на битах числа, поэтому числа в примерах будут в двоичной системе счисления.
Я расскажу о следующих побитовых операторах:
- | (Побитовое ИЛИ (OR)),
- & (Побитовое И (AND)),
- ^ (Исключающее ИЛИ (XOR)),
- ~ (Побитовое отрицание (NOT)),
- > (Побитовый сдвиг вправо).
Битовые операции изучаются в дискретной математике, а также лежат в основе цифровой техники, так как на них основана логика работы логических вентилей — базовых элементов цифровых схем. В дискретной математике, как и в цифровой технике, для описания их работы используются таблицы истинности. Таблицы истинности, как мне кажется, значительно облегчают понимание битовых операций, поэтому я приведу их в этой статье. Их, тем не менее, почти не используют в объяснениях побитовых операторов высокоуровневых языков программирования.
О битовых операторах вам также необходимо знать:
- Некоторые побитовые операторы похожи на операторы, с которыми вы наверняка знакомы (&&, ||). Это потому, что они на самом деле в чем-то похожи. Тем не менее, путать их ни в коем случае нельзя.
- Большинство битовых операций являются операциями составного присваивания.
Побитовое ИЛИ (OR)
Побитовое ИЛИ действует эквивалентно логическому ИЛИ, но примененному к каждой паре битов двоичного числа. Двоичный разряд результата равен 0 только тогда, когда оба соответствующих бита в равны 0. Во всех других случаях двоичный результат равен 1. То есть, если у нас есть следующая таблица истинности:
38 | 53 будет таким:
| A | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 |
|---|---|---|---|---|---|---|---|---|
| B | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 1 |
| A | B | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 1 |
В итоге мы получаем 1101112 , или 5510 .
Побитовое И (AND)
Побитовое И — это что-то вроде операции, противоположной побитовому ИЛИ. Двоичный разряд результата равен 1 только тогда, когда оба соответствующих бита операндов равны 1. Другими словами, можно сказать, двоичные разряды получившегося числа — это результат умножения соответствующих битов операнда: 1х1 = 1, 1х0 = 0. Побитовому И соответствует следующая таблица истинности:
Пример работы побитового И на выражении 38 & 53:
| A | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 |
|---|---|---|---|---|---|---|---|---|
| B | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 1 |
| A & B | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 |
Как результат, получаем 1001002 , или 3610 .
С помощью побитового оператора И можно проверить, является ли число четным или нечетным. Для целых чисел, если младший бит равен 1, то число нечетное (основываясь на преобразовании двоичных чисел в десятичные). Зачем это нужно, если можно просто использовать %2 ? На моем компьютере, например, &1 выполняется на 66% быстрее. Довольно неплохое повышение производительности, скажу я вам.
Исключающее ИЛИ (XOR)
Разница между исключающим ИЛИ и побитовым ИЛИ в том, что для получения 1 только один бит в паре может быть 1:
Например, выражение 138^43 будет равно…
| A | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 0 |
|---|---|---|---|---|---|---|---|---|
| B | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 1 |
| A ^ B | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 1 |
С помощью ^ можно поменять значения двух переменных (имеющих одинаковый тип данных) без использования временной переменной.
Также с помощью исключающего ИЛИ можно зашифровать текст. Для этого нужно лишь итерировать через все символы, и ^ их с символом-ключом. Для более сложного шифра можно использовать строку символов:
Исключающее ИЛИ не самый надежный способ шифровки, но его можно сделать частью шифровального алгоритма.
Побитовое отрицание (NOT)
Побитовое отрицание инвертирует все биты операнда. То есть, то что было 1 станет 0, и наоборот.
Вот, например, операция ~52:
| A | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 0 |
|---|---|---|---|---|---|---|---|---|
| ~A | 1 | 1 | 0 | 0 | 1 | 0 | 1 | 1 |
Результатом будет 20310
При использовании побитового отрицания знак результата всегда будет противоположен знаку исходного числа (при работе со знаковыми числами). Почему так происходит, узнаете прямо сейчас.
Дополнительный код
Здесь мне стоит рассказать вам немного о способе представления отрицательных целых чисел в ЭВМ, а именно о дополнительном коде (two’s complement). Не вдаваясь в подробности, он нужен для облегчения арифметики двоичных чисел.
Главное, что вам нужно знать о числах, записанных в дополнительном коде — это то, что старший разряд является знаковым. Если он равен 0, то число положительное и совпадает с представлением этого числа в прямом коде, а если 1 — то оно отрицательное. То есть, 10111101 — отрицательное число, а 01000011 — положительное.
Чтобы преобразовать отрицательное число в дополнительный код, нужно инвертировать все биты числа (то есть, по сути, использовать побитовое отрицание) и добавить к результату 1.
Например, если мы имеем 109:
| A | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 |
| ~A | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 |
| ~A+1 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 1 |
Представленным выше методом мы получаем -109 в дополнительном коде.
Только что было представлено очень упрощенное объяснение дополнительного кода, и я настоятельно советую вам детальнее изучить эту тему.
Побитовый сдвиг влево
Побитовые сдвиги немного отличаются от рассмотренных ранее битовых операций. Побитовый сдвиг влево сдвигает биты своего операнда на N количество битов влево, начиная с младшего бита. Пустые места после сдвига заполняются нулями. Происходит это так:
Побитовый сдвиг вправо
Как вы могли догадаться, >> сдвигает биты операнда на обозначенное количество битов вправо.
Если операнд положительный, то пустые места заполняются нулями. Если же изначально мы работаем с отрицательным числом, то все пустые места слева заполняются единицами. Это делается для сохранения знака в соответствии с дополнительным кодом, объясненным ранее.
Так как побитовый сдвиг вправо — это операция, противоположная побитовому сдвигу влево, несложно догадаться, что сдвиг числа вправо на N количество позиций также делит это число на 2 N . Опять же, это выполняется намного быстрее обычного деления.
Вывод
Итак, теперь вы знаете больше о битовых операциях и не боитесь их. Могу предположить, что вы не будете использовать >>1 при каждом делении на 2. Тем не менее, битовые операции неплохо иметь в своем арсенале, и теперь вы сможете воспользоваться ими в случае надобности или же ответить на каверзный вопрос на собеседовании.
1. Все адреса, используемые в современных компьютерных сетях – это 32-разрядные двоичные числа.
Для вычисления адреса сети компьютер применяет к адресу узла сети и маске, представленным в двоичном виде, операцию поразрядной конъюнкции. Это значит, что в определенном разряде итогового числа стоит 1 тогда и только тогда, когда у обоих исходных чисел в этом разряде стоит 1. При разборе задания эта операция обозначается символом &. Таким образом, ,
адрес_сети = адрес_узла & маска.
2. Чтобы пояснить операцию поразрядной конъюнкции, разберем несколько примеров. В этих примеров для удобства двоичные разряды рассматриваемых двоичных чисел собраны в группы по 4 разряда. Такие группы удобно обозначать 16-чными цифрами (полезная информация про системы счисления здесь) .
Пример 1. Пусть X = 1101; Y = 1011. Тогда X&Y = 1001 (только в первом и последнем разряде и в X, и в Y стоит 1).
Пример 2. Пусть X = 1101; Y = 0011. Тогда X&Y = 0001
Пример 3. Пусть X = 1111 1101; Y = 1010 0011. Тогда X&Y = 1010 0001
Пример 4. Пусть X = 1111 1111; Y = 1010 0011. Тогда X&Y = 1010 0011
Пример 5. Пусть X = 0000 0000; Y = 1010 0011. Тогда X&Y = 0000 0000
3. Работать с 32-разрядными двоичными числами человеку неудобно, поэтому для IP-адресов используют побайтное представление, записывая каждый байт (т.е. восьмерку двоичных разрядов, иногда говорят - октет) в десятичной системе счисления, например IP-адрес 11011001 11101001 11101000 00000011 можно записать как 217.233.232.3. Байты (точнее - их десятичные представления) принято отделять точками.
Свойства поразрядной конъюнкции, которые отмечены в примерах 4 и 5, можно записать так. Пусть A–целое число от 0 до 255, тогда
A & 255 = A
A & 0 = 0
4. При выполнении задания B11 полезно учитывать следующее.
- В маске подсети старшие (левые) байты всегда 255 (т.е. в них все разряды 1), младший байт (четвертый слева, т.е. самый правый) всегда 0 (т.е. в нем все разряды 0).
- В третьем слева байте слева стоит какое-то количество единиц и далее – нули.
Поэтому третье слева число в маске может принимать только такие значения:
. 128 = 1000 00002 = 255-127
. 192 = 1100 00002 = 128+64 = 255 – 63
. 224 = 1110 00002 = 128+64 + 32 = 255 – 31
. 240 = 1111 00002 = 128+64 + 32 + 16 = 255 – 15
. 248 = 1111 10002 = 128+64 + 32 + 16 + 8 = 255 – 7
. 252 = 1111 11002 = 128+64 + 32 + 16 + 8 +4 = 255 – 3
. 254 = 1111 11102 = 128+64 + 32 + 16 + 8 +4 +2 = 255 – 1
. 255 = 1111 11112 = 128+64 + 32 + 16 + 8 +4 +2 + 1
- первое и второе число в адресе сети те же, что и в адресе узла сети;
- четвертое – всегда 0;
- третье получается из третьего числа адресе узла сети обнулением определенного количества младших разрядов. Например, если третье число в маске подсети равно 248, то обнуляются три младших разряда третьего числа адреса узла подсети.
Осваивайте профессию, начните зарабатывать, а платите через год!
Курсы Python Акция! Бесплатно!
Станьте хакером на Python за 3 дня
Веб-вёрстка. CSS, HTML и JavaScript
Курс Bootstrap 4
Станьте веб-разработчиком с нуля
Побитовые (поразрядные) операторы & , | , ^ и ~ напоминают логические операторы, но их область действия — биты, а не логические значения. Среди побитовых операторов есть также операторы сдвига, позволяющие переместить все биты числа влево или вправо на нужно количество разрядов.
Формат 32-битного целого числа со знаком
Поразрядные (побитовые) операторы работают с 32-битными целыми числами в их двоичном представлении.
Двоичные числа представляют из себя строки, состоящие из нулей и единиц, в которых значение каждой единицы определяется ее позицией в данной строке.
Вот так, например, выглядият числа, записанные в формате 32-разрядного целого двоичного числа:
Каждый сдвиг влево на одну позицию означает удвоение значения, которое соответствует предыдущей позиции, находящейся справа.
Чтобы не путать, в какой системе счисления записано число, обычно в индексе пишут основание системы счисления, в которой оно записао. Например, число 5 в десятичной системе – 510,а в двоичной – 1012.
Чтобы перевести число в двоичную систему счисления необходимо делить его нацело на 2 пока не получим 0, затем необходимо записать все остатки от деления в обратном порядке.
Например, число 18, записываемое в двоичной системе счисления, имеет значение:
Теперь записываем полученные остатки от деления в обратном порядке. Получаем, что число 18 в двоичном представлении будет выглядеть как 00000000000000000000000000010010 (обратите внимание, число состоит ровно из 32-битов), или, сокращенно, как 10010. Эти пять значимых битов и определяют фактическое значение числа 18.
Для преобразования из двоичной системы в десятичную используют формулу, состоящую из степеней основания 2:
где а – число в десятичной системе счисления; a0, a1, … an – цифры данного числа в двоичном представлении. Причём a0 — это последняя или правая цифра, а an – первая.
Например, возьмём двоичное число 1010012. Для перевода в десятичное запишем его как сумму по разрядам следующим образом:
Перепишем тоже самое, возведя в степени все основания 2:
Можно записать это в виде таблицы следующим образом:
| 512 (2 10 ) | 256 (2 9 ) | 128 (2 8 ) | 64 (2 6 ) | 32 (2 5 ) | 16 (2 4 ) | 8 (2 3 ) | 4 (2 2 ) | 2 (2 1 ) | 1 (2 0 ) |
| 1 | 0 | 1 | 0 | 0 | 1 | ||||
| +32 | +0 | +8 | +0 | +0 | +1 |
Положительные числа хранятся в настоящем двоичном формате, в котором все биты, кроме знакового (крайний левый), представляют степени двойки: первый бит (справа) соответствует 2 0 , второй – 2 1 , третий – 2 2 и т. д. Если какие-либо биты не используются, они считаются равными нулю.
Теперь под каждой двоичной единицей напишите её эквивалент в нижней строчке таблицы и сложите получившиеся десятичные числа. Таким образом, двоичное число 1010012 равнозначно десятичному 4110.
К примеру, определим двоичное представление числа -5. Начнём с двоичного представления его абсолютного значения (5):
Инвертируем все разряды числа (заменим 0 на 1, а 1 на 0), получая таким образом обратный код (первое дополнение) числа 5:
Дополнительный код (второе дополнение) двоичного числа получается добавлением 1 (обычным двоичным сложением) к младшему значащему разряду его первого дополнения:
Итак, мы получили:
В целых числах со знаком все биты, кроме 32-го, представляют само значение, тогда как 32-й бит определяет знак числа: если крайний-левый бит равен 0 – число положительное, если 1 – число отрицательное. Поэтому этот бит называется знаковым битом.
При изучении побитовых операторов вам могут пригодиться функции, которые облегчают перевод чисел из десятичного в двоичное представление и наоборот:
Список побитовых операторов
В следующей таблице перечислены все побитовые (поразрядные) операторы JavaScript:
| Оператор | Использование | Описание |
|---|---|---|
| Побитовое И (AND) | a & b | Возвращает 1 в тех позициях результата, в которых биты каждого из операндов равны 1. |
| Побитовое ИЛИ (OR) | a | b | Возвращает 1 в тех позициях результата, в которых бит хотя бы одного из операндов равен 1. |
| Побитовое исключающее ИЛИ (XOR) | a ^ b | Возвращает 1 в тех позициях результата, в которых бит только одного из операндов равен 1. |
| Побитовое НЕ (NOT) | ~ a | Заменяет каждый бит операнда на противоположный. |
| Сдвиг влево | a | Сдвигает двоичное представление числа a на b разрядов влево заполняя освободившиеся справа разряды нулями. |
| Правый сдвиг, переносящий знак | a >> b | Сдвигает двоичное представление а на b разрядов вправо, отбрасывая уходящие биты. |
| Правый сдвиг с заполнением нулями | a >>> b | Сдвигает двоичное представление числа a на b разрядов вправо. Освобождающиеся разряды заполняются нулями. |
Побитовые операторы, подобно логическим операторам, выполняют логические операции И, ИЛИ, НЕ, XOR , но с каждым отдельным битом целого числа. Cреди побитовых операторов есть также операторы сдвига >, >>> позволяющие переместить все биты числа влево или вправо на нужно количество разрядов. Побитовые операторы преобразуют свои операнды в 32-битные целые числа, представленные последовательностью битов. Дробная часть, если она есть, отбрасывается. Получившаяся в результате выполнения последовательность бит интерпретируется как обычное число.
Побитовое И (&)
Таблица истинности для этой операции выглядит так:
| a | b | a & b |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
В следующем примере поразрядное И выполняется для чисел 38 и 3:
Как видите, только в одной позиции биты обоих операндов равны 1. Из-за этого все остальные биты результата обнуляются, что в итоге дает 000010. Как результат, получаем 0000102, или 210.
Побитовое ИЛИ (|)
Побитовое ИЛИ ( | ) выполняет булеву операцию дизъюнкции над каждой парой битов, которые стоят на одинаковых позициях в двоичных представлениях операндов. Другими словами, результат a | b равен 0, если оба соответствующих бита операндов равны 0; если же хотя бы один бит из пары равен 1, результирующий двоичный разряд равен 1.
Таблица истинности для этой операции выглядит так:
| a | b | a | b |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
В следующем примере поразрядное ИЛИ выполняется для чисел 38 и 3:
Каждый единичный бит любого из операндов переходит в результат. В итоге, получаем 1001112, или 3910.
Побитовое исключающее ИЛИ (^)
Побитовое исключающее ИЛИ ( ^ ) выполняет исключающую дизъюнкцию над каждой парой битов, которые стоят на одинаковых позициях в двоичных представлениях операндов. Другими словами, результат a ^ b равен 0, если оба соответствующих бита операндов равны между собой; в противном случае, двоичный разряд результата равен 1.
Таблица истинности для этой операции выглядит так:
| a | b | a ^ b |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
В следующем примере поразрядное исключающее ИЛИ выполняется для чисел 38 и 3:
Этот пример отличается от предыдущего только тем, что второй бит результата обнуляется, поскольку в обоих операндах он равен 1. Все остальные единичные биты переходят в результат, потому что у них нет пары. В итоге, получаем 1001012, или 3710.
Исключающее ИЛИ ( ^ ) с нулём в качестве одного из операндов можно использовать для округления математических выражений:
Учитывая, что у побитовых операторов достаточно низкий приоритет (ниже чем у арифметических операторов), скобки в приведенных выражениях могут быть опущены.
Побитовое НЕ (~)
Побитовое отрицание НЕ ( ~ ) – это унарный оператор, который возвращает обратный код числа. Другими словами, на той позиции, где в двоичном представлении операнда был 0, в результате будет 1, и, наоборот, где была 1, там будет 0.
Читайте также: