Лекция 8. Поразрядные операции
Введение
Информация в компьютере представляется в двоичной системе (наличие и отсутствие напряжения). Минимальной единицей информации является бит – ноль или единица, ложь или истина, «нет» или «да». Каждый байт состоит из 8 бит. Если число знаковое (signed), то самый левый его бит обозначает знак числа – 0 для положительных чисел и 1 для отрицательных чисел, остальные биты формируют модуль числа (это относится только к целым числам, вещественные числа всегда со знаком). Если число беззнаковое (unsigned), то все биты участвуют в формировании значения, но число может быть только положительным.
Положительные целые числа в компьютере представляются в нормальном коде – это обычное представление числа в двоичной системе, а отрицательные – в дополнительном коде. Для получения дополнительного кода берется двоичное представление равного по модулю целого числа, затем все цифры двоичного представления инвертируются (0 переходит в 1, 1 – в 0), при этом получается так называемый обратный код, к которому прибавляется 1 для получения дополнительного кода. Например, нормальный код числа 207 при использовании 2 байт – 0000000011001111, а дополнительный код числа -207 – 1111111100110001 (количество цифр в числе существенно!). Если сложить два эти числа, получается 0 (с переносом 1 за старший разряд числа). При сложении различных по модулю положительного и отрицательного чисел получается число в нормальном коде, если результат больше 0, и число в дополнительном коде, если результат меньше 0.
Существуют операции, которые работают с битами – можно взять отрицание, применить операции «И» или «ИЛИ». Поразрядные операции применяются к перечислениям и интегральным типами – bool, char, short, int и long (возможно, с модификатором unsigned). Однако нельзя применить эти операции к одному биту, а можно лишь применить одну и ту же операцию ко всем битам переменной.
1. Операции «отрицание» ~, «и» &, «или» |, «исключающее или» ^
| Система счисления | А | В | ~ А | А & В | А | В | А ^ В |
| Десятичная | 15 | 85 | 240 (-16) | 5 | 95 | 90 |
| Двоичная | 00001111 | 01010101 | 11110000 | 00000101 | 01011111 | 01011010 |
| Шестнадцатеричная | 0f | 55 | f0 | 05 | 5f | 5a |
Пример.
int a, b, c;
c = a & b;
c = a ^ b;
a |= 0x0f0f0f0f;
2. Операции сдвига
Операции сдвига вправо и сдвига влево сдвигают биты в переменной на заданное количество позиций. Существует три разновидности сдвига:
В языке Ассемблер существуют все три разновидности сдвига, в языке С++, однако, существует только одна операция сдвига влево и одна операция сдвига вправо. При сдвиге влево разницы между арифметическим и логическим сдвигом нет. При сдвиге вправо, если переменная объявлена как беззнаковая (unsigned), выполняется логический сдвиг, если же переменная объявлена как знаковая (по умолчанию) выполняется арифметический сдвиг.
| Система счисления | Число | unsigned char | signed char | ||
| << | >> | << | >> | ||
| Десятичная | 189 (-67) | 122 | 94 | 122 | -34 |
| Двоичная | 10111101 | 01111010 | 01011110 | 01111010 | 11011110 |
| Шестнадцатеричная | bd | 7a | 5e | 7a | de |
Пример.
| int a; | |
| unsigned int b; | |
| a = a << 2; | // Сдвиг влево, эквивалентен умножению на 4 |
| a >>= 2; | // Арифметический сдвиг вправо, деление на 4 |
| b >>= 3; | // Логический сдвиг вправо, деление на 8 |
3. Примеры
Пример 1. Функция, считающая количество единичных бит в числе
| int Bitcount(int x) | |
| { int c; | |
| unsigned mask = 0x80000000; |
// Вспомогательная переменная, с помощью которой выделяется один бит из числа // (за счет того, что все биты, кроме самого левого, после применения операции & // будут равны 0, самый левый бит останется без изменений). // Переменная инициализируется шестнадцатеричной константой 0x80000000, // в которой все биты, кроме самого левого, равны 0. |
| for (c = 0; x != 0; x <<= 1) | |
| if (x & mask) c++; | |
| return c; | |
| } |
Пример 2. Функция, устанавливающая заданный бит в 0
| int ClearBit(int x, int pos) | |
|
{ unsigned mask = 1; |
|
| if (0 <= pos && pos < 32) | |
| return x & (~(mask << pos)); | |
| return 0xFFFFFFFF; | // В случае ошибки возвращаем число, в котором все биты установлены в 1 |
| } |
Пример 3. Функция, устанавливающая заданный бит в 1
| int SetBit(int x, int pos) | |
|
{ unsigned mask = 1; |
|
| if (0 <= pos && pos < 32) | |
| return x | (mask << pos); | |
| return 0; | // В случае ошибки возвращаем число, в котором все биты установлены в 0 |
| } |
Пример 4. Функция, инвертирующая n бит, справа от позиции p (p отсчитывается с правого бита, начиная с 0)
| int Invert(int x, int p, int n, int *err) | |
| { unsigned mask = 0xFFFFFFFF; | |
|
unsigned t; |
|
| if (0 <= p && p < 32 && n <= p + 1) | |
| { mask = ~((mask >> (32 - n)) << (p + 1 - n)); | |
| t = (~(unsigned)x >> (32 - n)) << (p + 1 - n); | |
| x &= mask; | |
| x |= t; | |
| *err = 0; | |
| return x; | |
| } | |
| *err = 1; | |
| return 0; | |
| } |
Пример 5. Использование поразрядных операций для работы с атрибутами
|
#include <cstdio> |
|
| enum Rights | // Перечислитель Rights задаёт имена константам |
| { READ = 1, | // Используем степени числа 2 для того, |
| WRITE = 2, | // чтобы каждая константа содержала только один единичный бит |
| MODIFY = 4, | |
| DELETE = 8, | |
| ALL = 15 | // Для удобства |
|
}; |
|
| void SetRights(unsigned int &user, int r) | // Установка некоторого права |
|
{ user |= r; } |
|
| void UnsetRights(unsigned int &user, int r) | // Отмена права |
|
{ user &= ~r; } |
|
| void main() | |
|
{ unsigned int user1 = 0, user2 = 0; |
|
| SetRights(user1, READ | WRITE); | // Используем операцию | для объединения значений |
| SetRights(user2, ALL); | |
|
UnsetRights(user2, DELETE); |
|
|
if (user1 & READ) printf("User1 can read\n"); if (user1 & WRITE) printf("User1 can write\n"); if (user1 & MODIFY) printf("User1 can modify\n"); if (user1 & DELETE) printf("User1 can delete\n"); |
// Используем операцию & для проверки |
|
if (user2 & READ) printf("User2 can read\n"); if (user2 & WRITE) printf("User2 can write\n"); if (user2 & MODIFY) printf("User2 can modify\n"); if (user2 & DELETE) printf("User2 can delete\n"); |
|
| } |