Теоретический материал (С++)
Битовые операции
Скалярными типами данных называются все типы, принимающие целочисленные значения: char, short int, int, long int, long long, а также их signed и unsigned модификации.
Для хранения каждого из этих типов в памяти отводится определенное количество байт. Для того, чтобы узнать размер памяти, отводимый для хранения той или иной переменной можно использовать оператор sizeof: например, sizeof(int) возвращает количество байт, необходимых для хранения переменной типа int, а sizeof(A), где A – идентификатор переменной, возвращает количество байт, необходимой для хранения переменной A.
Каждую переменную скалярного типа будем представлять в виде последовательности бит, нумеруя их от 0, биты будем записывать справа налево (то есть бит с номером 0 будет записан самым правым, а самый старший бит – самым левым).
Например, если переменная a объявлена, как unsigned char, то ее можно записать в виде последовательности из 8 бит:
unsigned char a;
a=0 ; // 00000000
a=1 ; // 00000001
a=2 ; // 00000010
a=10 ; // 00001010
a=255 ; // 11111111
Например, если a=10, то в битовой записи a биты с номерами 1 и 3 равны 1, а остальные биты равны 0.
Для двух переменных одинакового скалярного типа определены битовые операции:
& битовое И (AND)
| битовое ИЛИ (OR)
^ битовое ИСКЛЮЧАЮЩЕЕ ИЛИ (XOR)
~ битовое ОТРИЦАНИЕ (NOT) - унарный оператор
Битовые операторы работают следующим образом. Берутся два операнда, и к каждой паре соответствующих бит для левого и правого операнда применяется данная операция, результатом будет переменная того же типа, каждый бит которой есть результат применения соответствующей логической операции к соответствующим битам двух операндов. Рассмотрим пример:
unsigned char a, b, c, d, e, f;
a = 5 ; // 00000101
b = 6 ; // 00000110
c = a & b ; // 00000100 == 4
d = a | b ; // 00000111 == 7
e = a ^ b ; // 00000011 == 3
f = ~ a ; // 11111010 == 250
Битовое отрицание числа (величина f в последнем примере) – это число, полученное из исходного заменой всех нулей на единицы и наоборот.
Будьте аккуратны, не путайте логические и битовые операции. Например, 2 && 1 == 1, поскольку применение логического "И" к двум значениям 2 и 1, то есть к двум "истинам", это истина, но 2 & 1 == 0!
Есть еще две операции, работающие с битами: это битовые сдвиги. Их две: сдвиг влево и вправо. Оператор a>>n возвращает число, которое получается из a сдвигом всех бит на n позиций вправо, при этом самые правые n бит отбрасываются. Например:
unsigned char a, b, c, d, e;
a = 43 ; // 00101011
b = a >> 1 ; // 00010101 == 21
c = a >> 2 ; // 00001010 == 10
d = a >> 3 ; // 00000101 == 5
e = a >> 5 ; // 00000001 == 1
Понятно, что для положительных чисел битовый сдвиг числа вправо на n равносилен целочисленному делению на 2n.
Аналогично, битовый сдвиг влево на n бит равносилен (для положительных чисел) умножению на 2n и осуществляется при помощи оператора <<:
unsigned char a;
a = 5 ; // 00000101
b = a << 1 ; // 00001010 == 10
c = a << 2 ; // 00010100 == 20
d = 2 << 3 ; // 00101000 == 40
Упражнения
Во всех упражнениях нельзя использовать арифметические операторы сложения, умножения, вычитания, деления. Вместо них используем побитовые операторы &, |, ~, ^, <<, >>.
Входное число A имеет тип unsigned int (за исключением последней задачи). Номера битов всегда задаются корректно, то есть принимают значения от 0 до 31.
- (A) Дано число n<32. Запишите число 2n, то есть число, у которого n-й бит равен 1, а остальные – нули.
- (B) Даны два неравных числа: n и m, не превосходящие 31. Вычислите 2n+2m.
- (C) Дано целое число A и натуральное число i. Обнулите у числа A его последние i бит и выведите результат.
- (D) Дано целое число A и натуральное число i. Выведите число, которое получается из числа A установкой значения i-го бита равному 1.
- (E) Дано целое число A и натуральное число i. Выведите число, которое получается из числа A инвертированием i-го бита.
- (F) Дано целое число A и натуральное число i. Выведите число, которое получается из числа A установкой значения i-го бита равному 0.
- (G) Дано целое число A и натуральное число n. Выведите число, которое состоит только из n последних бит числа A (то есть обнулите все биты числа A, кроме последних n).
- (H) Дано целое число A и натуральное число i. Выведите значение i-го бита числа A, то есть 0 или 1.
- (I) Дано число типа
unsigned char, то есть от 0 до 255. Выведите его в битовой форме: 8 бит, старшие биты слева, младшие – справа.
Самостоятельная работа
Напишите функцию printbyte(unsigned char x), печатающую данный байт побитово (как в последней задаче). Теперь реализуйте шаблон template <typename T> print (T A), который печатает переменную A данного типа T побитно. В шаблоне print объявим переменную p типа unsigned char * и сделаем так, чтобы она указывала на переменную A, для чего потребуется сделать явное преобразование типов:
unsigned char * p = (unsigned char *) &A;
Теперь, p[0] будет первым байтом переменной A, p[1] – следующим байтом и т.д. Значение каждого байта необходимо напечатать при помощи функции printbyte. Ну а общее количество байт в переменной A равно sizeof(A).
Теперь напишите функцию main, которая будет для некоторого типа считывать значение переменной данного типа и выводить его на экран побайтно при помощи шаблона print. Например, print( (short) 1) должен вывести 00000001 00000000, а print( (int) 1) должен вывести 00000001 00000000 00000000 00000000.
Теперь проведите эксперименты с различными типами данных с целью выяснения, как они хранятся в памяти. Начните с простых: unsigned char, unsigned short, unsigned int. Как записываются числа 0, 1, 2, 3? Какое наибольшее число можно записать в этих типах?
Разобрались с беззнаковыми числами? Переходим ко знаковым: как храняться отрицательные значения в типах signed char, signed short, signed int? Какие значения может принимать переменная этих типов? Попробуйте разобраться, как работают битовые сдвиги для отрицательных чисел.
Если удалось разобраться со знаковыми целыми – попробуйте перейти к действительным числам типов float и double. Это уже довольно трудная задача.