§ 27. Битовые операции в языке программирования
Site: | Профильное обучение |
Course: | Информатика. 10 класс (Повышенный уровень) |
Book: | § 27. Битовые операции в языке программирования |
Printed by: | Guest user |
Date: | Sunday, 13 October 2024, 4:41 PM |
Битовые операции также лежат в основе компьютерных устройств, так как на них основана логика работы логических вентилей — базовых элементов цифровых схем. Битовые операции по смыслу похожи на логические, но применяются для каждого разряда двоичного представления числа (бита) отдельно. Они определены только для целочисленных типов и не могут применяться к вещественным числам. В двоичном числе биты нумеруются справа налево, начиная с 0. С++ поддерживает все существующие битовые операции. (Рассмотрите пример 27.1.)
Таблицы истинности битовых и обычных логических операций И, ИЛИ, НЕ совпадают. Отличие лишь в том, что битовые операции выполняются над отдельными битами. Очевидно, что битовые операторы могут создать значения, отличные от 0 или 1. Логические же операторы всегда возвращают 0 или 1 (пример 27.2). Битовые операторы обычно не используются в условных операторах, которыми являются операторы отношения и логические операторы. Операторы сдвига >> и << сдвигают биты в переменной вправо и влево на указанное число. Общий вид оператора сдвига вправо: переменная >> число сдвигов; а общий вид оператора сдвига влево: переменная << число сдвигов; При побитовом сдвиге уходящий бит исчезает, не влияя на оставшиеся биты, а на месте появившегося бита записывается 0 (пример 27.3). При использовании битовых и логических операций, а также операций сравнения необходимо учитывать приоритет их выполнения (пример 27.4). Области применения битовых операций:
Рассмотрим использование битовых операций в С++ применительно к натуральным числам (примеры 27.9 — 27.16). Пример 27.9. Вычислить 2n + 2m.
а) сдвиг единицы влево на n позиций; б) сдвиг единицы влево на m позиций; в) побитовое OR с результатами сдвигов. Пример 27.10. Установить i-й бит числа A равным 1. Последовательно выполняется:
Пример 27.11. Инвертировать i-й бит числа A. Последовательно выполняется:
Пример 27.12. Установить i-й бит числа A равным 0. Последовательно выполняется:
Пример 27.13. Обнулить все биты числа A, кроме i битов. Последовательно выполняется:
Пример 27.14. Определить значение i-го бита числа A. Последовательно выполняется:
Пример 27.15. Посчитать количество единиц в двоичной записи числа A, заданного в десятичной системе счисления. Способ I
Способ II В цикле, который повторяем, пока A > 0, выполняем:
|
Пример 27.1. Выполнение битовых операций NOT, AND, OR, XOR.
Пример 27.3. Выполнение операций побитового сдвига.
Пример 27.4. Приоритет выполнения операций.
Пример 27.5. Если число является степенью двойки: int z = i & (i – 1) // z = 0 Если в двоичном представлении числа все единицы: int z = i & (i + 1) // z = 0 Пример 27.6. Обнуление крайнего правого единичного бита числа. A &= A - 1;
Пример 27.7. Обнуление крайних правых i бит числа.
Пример 27.8. Вычислить 2n.
1) n = m = 2:
A = 8. 2) n = 2, m = 3:
Пример 27.10.
A ^= (1 << i); 1) i = 3:
2) i = 2:
Пример 27.15. Вывести значение 8-разрядного числа побитно.
Способ I.
Способ II.
|
Вопросы к параграфу
1. С каким типом данных можно выполнять битовые операции? 2. Какие битовые операции реализованы в С++? В чем суть каждой из них? 3. Какие значения могут быть получены в результате выполнения битовых операций? 4. Какие приоритеты выполнения битовых, логических операций и операций сравнения установлены в С++? 5. В каких областях деятельности применяются битовые операции? |
Упражнения
1. Даны два натуральных числа a и b. Составить программу, реализующую для этих чисел битовую операцию по модулю два.
2. Вычислите xor всех чисел на отрезке [a, b].
3. Реализуйте программы из примера 27.16. Протестируйте для различных входных данных.
4. Дано число n. Используя битовые операции, замените единицу в младшем разряде двоичной записи числа n на ноль.
5. Даны два натуральных числа a и n. Найдите такое минимальное натуральное число b, что a xor b нацело делится на n.
6. Даны натуральные числа а и k. Выведите число, которое состоит только из k последних бит числа а (то есть, используя битовые операции, обнулите все биты числа а, кроме последних k).
7. Даны натуральные числа n и k. Используя битовые операции, обнулите в числе n его последние k бит и выведите результат.
8. Значением функции Фенвика для числа n называется максимальная степень двойки, на которую нацело делится число n. По заданному числу n определите для него значение функции Фенвика.
9. Дано натуральное число. Определите, сколько раз встречаются две подряд идущие единицы (11) в двоичном представлении этого числа (в двоичном представлении 11110111 оно встречается 5 раз).
10. Дано натуральное десятичное число n. Поменяйте местами два бита с заданными номерами в двоичном представлении этого числа. Например, если n = 5 и требуется поменять биты с номерами 1 и 2, то ответом будет 3.
11. Дано натуральное десятичное число n. Вычеркните i-й бит из двоичного представления этого числа (младшие i-го биты остаются на месте, старшие сдвигаются на один разряд вправо). Например, если n10 = 29 (n2 = 111012) и i = 1, ответом будет 1510 (11112).
12. Даны три натуральные числа. Найдите новое число, каждый бит которого равен тому значению, которое встречается чаще среди битов с таким же номером у данных чисел.
13. Для настольной игры используются карточки с номерами от 1 до n (натуральное число n не превышает 106). Одна карточка потерялась. Составьте программу ее поиска. Задано: число n и n - 1 номеров оставшихся карточек.
14. Дома у Ксюши было 2 одинаковых набора кубиков из английских букв, но во время очередной уборки один из кубиков затерялся. Помогите Ксюше определить, какой из кубиков отсутствует в одном из наборов.
15. Дано натуральное десятичное число n. Образуются все возможные левые циклические сдвиги двоичного представления числа n, у которых первая цифра числа переносится в конец.
Например, если n = 1110 (10112), то его циклические сдвиги: 01112, 11102, 11012, 10112. Максимальное значение m у всех полученных таким образом чисел будет иметь число 11102 = 1410.
Составьте программу, которая для заданного числа n определяет максимальное значение m.
16. Дано натуральное число n. С этим числом разрешено неограниченное количество раз проводить перестановку значащих бит заданного числа, получая таким образом новые числа. Найдите наибольшую разность двух чисел, каждое из которых можно получить в результате выполнений таких перестановок.
17. Дано натуральное число a. Напишите выражение, результатом которого является значение данного числа, у которого младший нулевой бит установлен в 1.
18. Дано натуральное число a. Напишите выражение, результатом которого является преобразование данного числа в число, у которого все биты установлены в 1, кроме младшего нулевого бита.