Печатать книгуПечатать книгу

§ 27. Битовые операции в языке программирования

Сайт: Профильное обучение
Курс: Информатика. 10 класс (Повышенный уровень)
Книга: § 27. Битовые операции в языке программирования
Напечатано:: Гость
Дата: Суббота, 27 Апрель 2024, 23:21

Оглавление

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

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

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

Операция

Знак операции

Отрицание NOT

~

Побитовое AND

&

Побитовое OR

|

Сложение по модулю два XOR

^

Сдвиг влево

<< 

Сдвиг вправо

>> 

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

Очевидно, что битовые операторы могут создать значения, отличные от 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. Вычислить 2n + 2m.

  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.

Пример 27.1. Выполнение битовых операций NOT, AND, OR, XOR.

Битовое NOT

Переменная

Значение

Двоичное
представление

X

44

0010 1100

X

211

1101 0011

int x = 44, z;

  z = ~x;

  cout << z << endl;  //211

Побитое AND

Переменная

Значение

Двоичное
представление

X

14

0000 1110

Y

11

0000 1011

X & Y

10

0000 1010

int x = 14, y = 11, z;

  z = x & y;

  cout << z << endl;  //10

Побитовое OR

Переменная

Значение

Двоичное
представление

X

10

0000 1010

Y

9

0000 1001

X | Y

11

0000 1011

int x = 10, y = 9, z;

 z = x | y;

 cout << z << endl;  //11

  

Побитовое XOR

Переменная

Значение

Двоичное
представление

X

10

1010 1100

Y

9

0010 0100

begin mathsize 14px style space straight X space to the power of logical and space straight Y end style

3

1000 1000

int x = 172, y = 36, z;

 z = x ^ y;

 cout << z << endl;  //136 

Пример 27.2.

int x = 10, z1, z2;

z1 = x & 8;

cout << z1 << endl;  //8

z2 = x && 8;

cout << z2 << endl;  //1

Пример 27.3. Выполнение операций побитового сдвига.

Сдвиг влево

Переменная

Значение

Двоичное
представление

     X

10

00001010

     Y = X << 1

20

000010100

     Y = X << 2

 40           0000101000
     Y = X << 3 80 00001010000

     Y = X << 5

64

0000101000000

 

int x = 10, z;

z = x << 2;

cout << z << endl;  //40

Сдвиг вправо
Переменная Значение Двоичное
представление
  X 10 00001010
  Y = X >> 1 5 000001010
  Y = X >> 2 2 0000001010
  Y = X >> 3 1 00000001010
  Y = X >> 5 0 0000000001010

int x = 10, z;

z = x >> 3;

cout << z << endl;  //1

  Пример 27.4. Приоритет выполнения операций.

Операция

Описание

>>, <<

 Побитовые сдвиги

>, <, >=, <=

Операции сравнения (1)

==, !=

Операции сравнения (2)

&

 Побитовые AND

^

 Побитовые XOR

|

 Побитовые OR

&&

 Логическое AND

||

 Логическое OR

Пример 27.5.

Если число является степенью двойки:

      int z = i & (i – 1) // z = 0    

Если в двоичном представлении числа все единицы:

      int z = i & (i + 1) // z = 0    

Пример 27.6. Обнуление крайнего правого единичного бита числа.

     A &= A - 1;   

A

1000 1010

A — 1

1000 1001

&

1000 1000

Пример 27.7. Обнуление крайних правых i бит числа.

i = 2;

A >>= i;

A <<= i;

A

1000 1011

>> 2

0010 0010

<< 2

1000 1000

Пример 27.8. Вычислить 2n. 

n = 2;

A = 1 << n;  // A = 4

A

0000 0001

<< 2

0000 0100

Пример 27.9.

if (n == m)

  A = 1 << (n + 1);

else

  A = 1 << n | 1 << m;

1) n = m = 2:

A

0000 0001

<< (2 + 1)

0000 1000

A = 8.

2) n = 2, m = 3:

 

0000 0001

<< 2

0000 0100

A = 4

 

0000 0001

<< 3

0000 1000

A = 8

|

0000 1100

A = 12

Пример 27.10.

i = 2;

A |= (1 << i);

A

1000 1011

 

0000 0001

<< 2

0000 0100

|

1000 1110

Пример 27.11.

           A ^= (1 << i);          

1) i = 3:

A

1000 1011

 

0000 0001

<< 3

0000 1000

^

1000 0011

2) i = 2:

A

1000 1011

 

0000 0001

<< 2

0000 0100

^

1000 1111

Пример 27.12.

i = 3;

A &= ~(1 << i);

A

1000 1011

 

0000 0001

<< 3

0000 1000

~

1111 0111

&

1000 0011

Пример 27.13.

i = 4;

A &= (1 << i) - 1;

A

1001 1011

 

0000 0001

<< 4

0001 0000

– 1

0000 1111

&

0000 1011

Пример 27.14.

i = 3;

int z = (A >> i) & 1;

  

A

1001 1011

>> 3

0001 0011

 

0000 0001

&

0000 0001

Пример 27.15. Вывести значение 8-разрядного числа побитно.

for (int i = 7; i >= 0; i--)

 cout << (A >> i & 1);

Пример 27.16.

Способ I.

 int bit;

 int mask = 1;
 int num = 0; 
 for (int i = 0; i <= 31; i++)
 {

   bit = mask & A;

   if (bit == mask)

      num++;
   mask = mask << 1;
 }

Способ II.

 int cnt = 0;
 while (A != 0)

 {

    A = (A – 1) & A;

    cnt++;

 }

Шаг цикла

Переменная

Значение

1

A

1000 1001

A - 1

1000 1000

&

1000 1000

cnt

1

2

A

1000 1000

A - 1

1000 0111

&

1000 0000

cnt

2

3

A

1000 0000

A - 1

0111 1111

&

0000 0000

cnt

3

Вопросы к параграфу

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, кроме младшего нулевого бита.