Информатика. 10 класс (Повышенный уровень)

Битовые операции также лежат в основе компьютерных устройств, так как на них основана логика работы логических вентилей — базовых элементов цифровых схем.

Битовые операции по смыслу похожи на логические, но применяются для каждого разряда двоичного представления числа  (бита) отдельно. Они определены только для целочисленных типов и не могут применяться к вещественным числам. В двоичном числе биты нумеруются справа налево, начиная с 0.

С++ поддерживает все существующие битовые операции. (Рассмотрите пример 27.1.)

Таблицы истинности битовых и обычных логических операций И, ИЛИ, НЕ совпадают. Отличие лишь в том, что битовые операции выполняются над отдельными битами.

Очевидно, что битовые операторы могут создать значения, отличные от 0 или 1. Логические же операторы всегда возвращают 0 или 1 (пример 27.2). Битовые операторы обычно не используются в условных операторах, которыми являются операторы отношения и логические операторы.

Операторы сдвига >> и << сдвигают биты в переменной вправо и влево на указанное число.

Общий вид оператора сдвига вправо:

переменная >> число сдвигов;

а общий вид оператора сдвига влево:

переменная << число сдвигов;

При побитовом сдвиге уходящий бит исчезает, не влияя на оставшиеся биты, а на месте появившегося бита записывается 0 (пример 27.3).

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

Области применения битовых операций:

1. Проверка, сброс и установка отдельных битов в составе числа.
2. Выполнение быстрого умножения и деления (сдвиг влево равносилен умножению на 2, а сдвиг вправо — делению на 2).
3. Экономия памяти (упаковка нескольких логических значений в одну целую переменную).
4. Повышение производительности программ — битовые операции могут выполняться одновременно со всеми разрядами.
5. При разработке драйверов устройств, например программ для модемов, дисков и принтеров.
6. При декодировании информации от внешних устройств.
7. В шифровании.

Рассмотрим использование битовых операций в С++ применительно к натуральным числам (примеры 27.9 — 27.16).

Пример 27.9. Вычислить 2ⁿ + 2^m.

1. При n = m выполняется сдвиг единицы влево на n + 1 позицию.
2. При n ≠ m выполняется последовательно:

а) сдвиг единицы влево на n позиций;

б) сдвиг единицы влево на m позиций;

в) побитовое OR с результатами сдвигов.

Пример 27.10. Установить i-й бит числа A равным 1.

Последовательно выполняется:

1. Сдвиг единицы влево на i позиций.
2. Побитовое OR числа A с результатом сдвига единицы.

Пример 27.11. Инвертировать i-й бит числа A.

Последовательно выполняется:

1. Сдвиг единицы влево на i позиций.
2. Побитовое XOR числа A с результатом сдвига единицы.

Пример 27.12. Установить i-й бит числа A равным 0.

Последовательно выполняется:

1. Сдвиг единицы влево на i позиций.
2. Инверсия результата сдвига единицы.
3. Побитовое AND числа A с результатом инверсии сдвига единицы.

Пример 27.13. Обнулить все биты числа A, кроме i битов.

Последовательно выполняется:

1. Сдвиг единицы влево на i позиций.
2. Вычитание 1 из результата сдвига единицы.
3. Побитовое AND числа A с результатом вычитания.

Пример 27.14. Определить значение i-го бита числа A.

Последовательно выполняется:

1. Сдвиг числа A вправо на i позиций.
2. Побитовое AND сдвига числа A с единицей.

Пример 27.15. Посчитать количество единиц в двоичной записи числа A, заданного в десятичной системе счисления.

Способ I

1.  Заводим битовую «маску» (переменная mask), содержащую единственный ненулевой бит в младшем разряде (32-разрядное двоичное число).
2. Позиция ненулевого бита меняется в цикле от младшего к старшему.
3. Если текущий бит числа A равен 1, то результат побитового AND очередного значения маски на значение числа A совпадает с маской. Этот факт используется для увеличения счетчика num.

Способ II

В цикле, который повторяем, пока A > 0, выполняем:

1.  Убираем крайнюю справа единицу в двоичном представлении числа A. Для этого изменяем значение числа A на результат побитового AND числа A и (A – 1). Результатом этого действия будет удаление в числе A единицы в младшем разряде.
2. Увеличиваем значение счетчика единиц cnt в числе A на 1.