Лекция 1. Битовые операции

Лекция 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

Операция сдвига влево целого числа на к разрядов эквивалентна умножению числа на 2^k, а сдвига вправо - делению числа на 2^k, но операции сдвига выполняются быстрее, чем умножение или деление.

Однако при сдвиге влево в знаковый бит может попасть цифровой разряд числа, это ситуация переполнения, она не замечается, но получившийся результат не равен умножению числа на 2^k.

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В₁₆= -111 1011₂

-123: 11111111 11111111 11111111 10000101

В16-ом коде: FF FF FF 85

Алгоритм “Быстрая степень” Рассмотрим возведение an, где n- целое, положительное число. Алгоритм основан…  

Представление вещественных чисел в памяти ПК

вещественной арифметики выполняет сопроцессор (FPU). Значение, полученное в сопроцессоре, преобразуется в тип float или doubleи… Вещественное число представляется в виде (в IBM PC):

P’= p+127 p’= p+1023 p’= p+16383

Для чисел X: 0< p’ <max;

 

Eсли P’=0 и f=0, то X=0.

+бесконечность : 0 11 . . .11 00. . . . 00 - бесконечность : 1 11 . . .11 00. . . . 00 P’ f

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

L= 1024* lg 2=1024*0.30103=308.25472

__[\\\\\\\\] _____|_____[\\\\\\\\]______ –Xmax -Xmin 0 Xmin Xmax Точность чисел, представленных в формате с плавающей точкой: часто вместо числа Х в МС хранится его приближение Х*.…

Double сохраняется в памяти 15-16 десятичных знаков.

Выполнение операций над числами, представленными с плавающей точкой (говорят- в плавающей арифметике).

a)Сложение (вычитание) чисел: Z = X ± Y = Mx×2Px ± My×2Py ={1шаг–выравнивание порядков к… = 2Px×(Mx ± My×2Py–Px) = {2 шаг–сдвиг мантиссы My на |Py–Px| разрядов}

Достоинства формы представления чисел с плавающей точкой.

· Хранение только значащих цифр числа. Представление обеспечивает для числа максимальную точность при фиксированной разрядной сетке. Недостатки формы представления чисел с плавающей точкой: · более сложная конструкция схем, выполняющих операции над числами в процессоре: необходимы отдельные схемы для…