Побитовые операции и дополнительный код
Побитовая операция применяет логическую операцию к каждой паре двоичных разрядов двух целых чисел отдельно. Сдвиги переносят все разряды влево или вправо, а «исключающее ИЛИ» с ключом шифрует и расшифровывает данные. В памяти целое число занимает фиксированное число бит, поэтому его диапазон ограничен, а отрицательное число хранится в дополнительном коде.
Биты целого числа
Побитовые операции работают с двоичной записью целых чисел, разряд за разрядом. Двоичную запись даёт перевод в двоичную систему.
- Поразрядная конъюнкция
a & b: 1 только там, где 1 в обоих числах. Дизъюнкцияa | b: 1 там, где 1 хотя бы в одном. «Исключающее ИЛИ»a ^ b: 1 там, где биты разные. - , если у нули во всех разрядах, где у единицы.
- Сдвиг влево на — умножение на , сдвиг вправо на — целое деление на .
- В битах без знака хранятся числа от 0 до , со знаком — от до .
- Дополнительный код отрицательного числа: запишите модуль в битах, инвертируйте все биты и прибавьте 1. То же число равно .
Побитовые логические операции
Побитовая операция применяет логическую операцию к каждому разряду отдельно: разряд 0 первого числа с разрядом 0 второго, разряд 1 с разрядом 1 и так далее. Переносов между разрядами нет. Запишите оба числа в двоичной системе одинаковой длины, дополнив короткое нулями слева, и вычислите столбик за столбиком. Сами операции И, ИЛИ, НЕ разобраны в блоке отрицание, конъюнкция и дизъюнкция.
В Python поразрядная конъюнкция — a & b, дизъюнкция — a | b, «исключающее ИЛИ» — a ^ b. Инверсия ~a у неограниченных целых Python даёт , поэтому для бит её берут с маской: ~a & 255 для восьми бит. В ЕГЭ поразрядную конъюнкцию обозначают .
Пример
Вычислите , поразрядную дизъюнкцию и «исключающее ИЛИ» чисел 14 и 5.
- 1., .
- 2.Конъюнкция: единица только в разряде 2, где 1 у обоих чисел: .
- 3.Дизъюнкция: единица в каждом разряде, где она есть хотя бы у одного числа: .
- 4.«Исключающее ИЛИ»: единица там, где биты разные: . Программа печатает 4 15 11.
Ответ: 4, 15 и 11
Побитовые операции над одним разрядом
| a | b | Конъюнкция | Дизъюнкция | Исключающее ИЛИ |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 0 |
Конъюнкция с маской: какие биты числа равны 1
Число в выражении работает как маска: результат сохраняет биты в тех разрядах, где у единицы, и обнуляет остальные. Поэтому значит: во всех единичных разрядах маски у стоят нули. А значит: хотя бы в одном единичном разряде маски у стоит 1.
Отдельный бит проверяют маской из одной единицы: , только если разряд числа равен 1. На этом стоят задачи задания 15 с поразрядной конъюнкцией: поразрядная конъюнкция в задании 15.
Пример
Сколько чисел от 0 до 15 удовлетворяют условию ?
- 1.: единицы маски в разрядах 3 и 2.
- 2.Условие верно, если у разряды 3 и 2 равны 0. Разряды 1 и 0 любые.
- 3.Таких четырёхбитных чисел : это 0, 1, 2 и 3. Программа перебирает и печатает 4.
Ответ:
Логический, арифметический и циклический сдвиги
Сдвиг переносит все биты числа на разрядов влево или вправо. Биты, которые вышли за край разрядной сетки, пропадают. При логическом сдвиге освободившиеся разряды заполняются нулями. Арифметический сдвиг вправо заполняет освободившиеся старшие разряды копией знакового бита, поэтому знак числа сохраняется. Арифметический сдвиг влево совпадает с логическим. При циклическом сдвиге бит, который выходит с одного края, входит с другого, и биты не теряются.
Сдвиг влево на умножает число на , если единицы не вышли за край. Сдвиг вправо на — целое деление на . В Python x << k — сдвиг влево, x >> k — арифметический сдвиг вправо: -78 >> 1 даёт . Разрядную сетку из восьми бит задают маской & 255.
Пример
Байт сдвинули на один разряд: логически влево, циклически влево, логически вправо и арифметически вправо. Запишите результаты.
- 1.Логически влево: старшая 1 уходит, справа входит 0: .
- 2.Циклически влево: старшая 1 уходит и входит справа: .
- 3.Логически вправо: младший 0 уходит, слева входит 0: .
- 4.Арифметически вправо: слева входит копия знакового бита 1: . Программа печатает первые три строки, четвёртую даёт
-78 >> 1.
Ответ: , , ,
Шифрование «исключающим ИЛИ»
«Исключающее ИЛИ» обозначают знаком . Пусть — исходные данные, — ключ, число той же длины. Тогда . Бит ключа 1 меняет бит данных, а второе применение того же бита меняет его обратно. Поэтому один и тот же ключ и шифрует, и расшифровывает: шифр — , расшифровка — . Текст шифруют побайтно: код каждого символа соединяют с ключом операцией ^.
Пример
Байт зашифровали ключом . Найдите шифр и расшифруйте его.
- 1.Шифр: биты разные в разрядах 6, 5, 2, 1 и 0, там 1: .
- 2.Расшифровка тем же ключом: , исходный байт.
- 3.В десятичной записи:
77 ^ 42даёт 103,103 ^ 42даёт 77.
Ответ: шифр
Беззнаковые числа и переполнение
В памяти компьютера целое число занимает фиксированное число бит , это разрядная сетка. Беззнаковое число использует все бит для значения, поэтому диапазон — от 0 до : в байте от 0 до 255, в 16 битах от 0 до 65535.
Если результат действия не помещается в сетку, старшие разряды теряются. Это переполнение: в сетке остаётся остаток от деления результата на . Целые числа Python не ограничены и не переполняются, поэтому -битную сетку в программе моделируют выражением x % 2**n.
Пример
В беззнаковых байтах сложили 200 и 100. Какое число получилось в байте?
- 1.Сумма больше 255, произошло переполнение.
- 2.. Девятый бит не помещается в байт и теряется.
- 3.Остаётся , то есть .
Ответ:
Знаковый бит и дополнительный код
В числе со знаком старший бит — знаковый бит: 0 у неотрицательных чисел, 1 у отрицательных. Отрицательное число хранится в дополнительном коде: запишите модуль числа в битах, инвертируйте все биты и прибавьте 1. Результат равен . Диапазон -битных чисел со знаком — от до : в байте от до 127.
Обратный перевод: если знаковый бит равен 1, число равно коду минус . Код в байте — это . В Python дополнительный код из восьми бит даёт format(x % 256, '08b'). Дополнительный код нужен, чтобы вычитание выполнялось как сложение: , а лишний перенос за сетку отбрасывается.
Пример
Запишите число в восьмибитном дополнительном коде.
- 1.Модуль в восьми битах: .
- 2.Инвертируем все биты: .
- 3.Прибавляем 1: . Знаковый бит 1, число отрицательное.
- 4.Проверка: . Программа печатает ту же строку.
Ответ:
Проверьте себя
00