Лекция 1. Битовые операции.
Битовые (поразрядные) операции применяются к целым операндам и выполняются над их двоичными представлениями. Стандартные типы , кроме вещественных, в С++ являются целыми, т.е. к данным этих типов (int, short, char, bool) могут быть применены поразрядные операции. Выполняется битовая операция над соответствующими битами операндов и результат операции записывается в соответствующий бит результата.
Рисунок 1. Схема битовой операции
Операции:
&- поразрядная конъюнкция (И) двоичных представлений операндов целого типа. Бит результата равен 1 тогда и только тогда, если соответствующие биты операндов равны 1.
7 & 5= 5 7: 00000111
5: 00000101
Результат 5: 00000101
Операция используется для выделения из битового представления части разрядов, такие разряды умножаются на 1 (по операции &).
| – поразрядная дизъюнкция (ИЛИ) двоичных представлений операндов целого типа. Бит результата равен 1, если хотя бы один из соответствующих битов операндов равен 1.
7 | 5= 7 7: 00000111
5: 00000101
Результат 7: 00000111
Операция используется для приформирования 1 некоторым разрядам битового представления, к этим разрядам добавляются 1 (по операции |).
^ - поразрядное исключающее ИЛИ двоичных представлений операндов целого типа. Бит результата равен 1, если соответствующие биты операндов различны.
7 ^ 5= 2 7: 00000111
5: 00000101
Результат 2: 00000010
Операция используется для инвертирования некоторых разрядов битового представления, такие разряды в операции исключающего ИЛИ обрабатываются 1.
~ - поразрядное отрицание (одноместная операция) инвертирует каждый разряд двоичного представления операнда.
~ 5 =-6 5: 00000101
Результат - 6 : 11111010 –дополнительный код числа -6
Операции сдвига
Применяются к целочисленным операндам:
ОП1 << ОП2 (сдвиг влево) или ОП1 >> ОП2(сдвиг вправо)
Двоичное представление ОП1 сдвигается влево (<<)) или вправо (>>) на количество двоичных разрядов, равное второму операнду ОП2.
При сдвиге вправо освободившиеся разряды заполняются знаковым разрядом (при сдвиге знаковых операндов) и нулём для беззнаковых. Вышедшие за разрядную сетку биты теряются.
5>>2 = 1 00000101 =>00000001 - результат = 1
(-5)>>2 = -2 11111011 =>11111110 -дополнительный код -2.
При сдвиге влево освободившиеся разряды заполняются нулями.
5<<2 = 00000101 =>00010100 - результат = 20
(-5)<<2 = 11111011 =>11101100 - дополнительный код-20
Операция сдвига влево целого числа на к разрядов эквивалентна умножению числа на 2k, а сдвига вправо - делению числа на 2k, но операции сдвига выполняются быстрее, чем умножение или деление.
Однако при сдвиге влево в знаковый бит может попасть цифровой разряд числа, это ситуация переполнения, она не замечается, но получившийся результат не равен умножению числа на 2k.
cout<<(2147483647<<1)<<" "<<(-2147483647<<1)<<'n'; // результат -2 2
Не следует путать битовые операции с логическими:
!0 – имеет значение истины, а ~0 представляет конечную последовательность единиц(т.е. -1).
Cout<<(!0)<<" "<<(~0)<<'n'; результат : 1 -1
Примеры использования битовых операций:
unsigned int n,m; (или int n,m; но n,m –не отрицательные)
If (n&1){ . . .} – проверяет, является ли n нечётным.
If (n&m){ . . .} - проверяет, есть ли у n и m совпадающие соответствующие биты.
If (n^m){ . . .} - проверяет, есть ли у n и m несовпадающие соответствующие биты.
4. If (n&(n-1)){ . . .}– проверяет, что n не является степенью 2. Если n есть степень 2, то n представляется в двоичном виде:
n: 00…01000…000,
а n-1: 00…00111…111,
Их произведение n&(n-1)=0.
Битовые операции и операции сдвига используются часто
Ø в выражениях, где они предпочтительнее других операций, т.к. выполняются быстрее;
Ø для реализации множеств небольшого размера. Множество представляется в виде конечной последовательности битов (вектора битов), бит есть элемент множества, каждому биту соответствует элемент некоторого, например, массива чисел, размер множества чисел ограничен количеством битов в векторе.
A[n-1] A[n-2] . . . . . . . . . . . . . . . . . . . . A[2] A[1] A[0]
Оператор typedef служит для того, чтобы задать новое имя некоторому типу: typedef тип новое_имя [размерность];
Например:
typedef int tip; //стандартный тип int назван новым именемtip. Алгоритм описывается для этого нового имени tip. В дальнейшем, если необходимо алгоритм использовать для нового имени, например short, надо будет изменить только оператор typedef: typedef short tip;
Размерность необязательна. Новое имя может использоваться также, как стандартные имена:
typedef char tipmas [50]; // tipmas это char[50]
Tipmas M[20]; M – это массив из 20 строк по 50
символов. (char MM [20][50])
const int L=sizeof(tip);
//Внутреннее представление целых данных
typedef int tip;
void inint (tip n, char s[])
{ // Двоичное представление целого данного n в строке s
int i, l;
L=sizeof(tip)<<3; // размер битовой строки для типа tip
I=l-1; // l-ый разряд- конец строки
Do
S[i--]=(char)((n&1)+'0'); //формирование i-го символа
N=n>>1; //сдвиг числа n вправо
}
While (i>=0); //цикл пока все символы не сформируются
S[l]=0; //символ 0 в конце сформированной строки
}
void inint16(tip n, char s[])
{// 16-теричное представление целого n в строке s.
int i,l;
Char alf[]="0123456789ABCDEF"; // 16-ричный алфавит
L=sizeof(tip)<<1; //размер 16-теричной строки для tip
i=l-1;
Do
S[i--]=alf[n&15]; //формирование i-го символа
N=n>>4; //сдвиг числа n вправо
}
While (i>=0); //цикл пока все символы не сформируются
S[l]=' '; //символ 0 в конце сформированной строки
}
Пример. Внутреннее представление целого числа -123 в слове: - 123=-7В16= -111 10112
-123: 11111111 11111111 11111111 10000101
P’= p+127 p’= p+1023 p’= p+16383
Для чисел X: 0< p’ <max;
7 6 5 4 3 0
16-ый код: 40 0С 00 00 00 00 00 00
Число –3.5: С0 0С 00 00 00 00 00 00
Диапазон чисел, представимых в формате с плавающей точкой (тип double): |X|min <=|X|<=|X|max и X=0 1<=P’<=2046
M|min*2pmin <=|X| <=|M|max*2pmax и X=0
Lt;=|X| <=(2-2-52)*21023 и X=0
K<=|X| <=10L lg2=0.30103
K= –1022*lg 2= –307.65266= -308+0.34734
Double сохраняется в памяти 15-16 десятичных знаков.