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

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

Битовые операции по смыслу похожи на логические, но применяются для каждого разряда двоичного представления числа  (бита) отдельно. Они определены только для целочисленных типов и не могут применяться к вещественным числам. В двоичном числе биты нумеруются справа налево, начиная с 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