Арифметический сдвиг (правый)

Арифметический сдвиг аналогичен логическому, но значение слова считается знаковым числом, представленным в дополнительном коде. Так, при правом сдвиге старший бит сохраняет свое значение. Левый арифметический сдвиг идентичен логическому.

Арифметические сдвиги влево и вправо используются для быстрого умножения и деления на 2.

Циклический сдвиг

При циклическом сдвиге, значение последнего бита по направлению сдвига копируется в первый бит (и копируется в бит переноса).

Циклический сдвиг через перенос

Первый бит по направлению сдвига получает значение из бита переноса, а значение последнего бита сдвигается в бит переноса.

Побитовое И (&)

Побитовое И — это бинарная операция, действие которой эквивалентно применению логического И к каждой паре битов, которые стоят на одинаковых позициях в двоичных представлениях операндов. Другими словами, если оба соответствующих бита операндов равны 1, результирующий двоичный разряд равен 1; если же хотя бы один бит из пары равен 0, результирующий двоичный разряд равен 0.

Пример:

&
=

Побитовое ИЛИ (|)

Побитовое ИЛИ — это бинарная операция, действие которой эквивалентно применению логического ИЛИ к каждой паре битов, которые стоят на одинаковых позициях в двоичных представлениях операндов. Другими словами, если оба соответствующих бита операндов равны 0, двоичный разряд результата равен 0; если же хотя бы один бит из пары равен 1, двоичный разряд результата равен 1.

Пример:

|

Исключающее ИЛИ (^)

Исключающее ИЛИ (или сложение по модулю 2) — это бинарная операция, результат действия которой равен 1, если число складываемых единичных битов нечётно и равен 0, если чётно.

Пример:

^

 

Рассмотрим простой пример. Пусть у нас есть класс из 30 студентов. Каждую неделю преподаватель проводит зачет, результат которого – сдал/не сдал. Итоги можно представить в виде битового вектора. (Заметим, что нумерация битов начинается с нуля, первый бит на самом деле является вторым по счету. Однако для удобства мы не будем использовать нулевой бит; таким образом, студенту номер 1 соответствует бит номер 1. В конце концов, наш преподаватель – не специалист в области программирования.)

unsigned int quiz1 = 0;

Нам нужно иметь возможность менять значение каждого бита и проверять это значение. Предположим, студент 27 сдал зачет. Бит 27 необходимо выставить в 1, не меняя значения других битов. Это можно сделать за два шага. Сначала нужно начать с числа, содержащего 1 в 27-м бите и 0 в остальных. Для этого используем операцию сдвига:

1 << 27;

Применив побитовую операцию ИЛИ к переменной quiz1 и нашей константе, получим нужный результат: значение 27-й бита станет равным значение 1, а другие биты останутся неизменными.

quiz1 |= 1<<27;

Теперь представим себе, что преподаватель перепроверил результаты теста и выяснил, что студент 27 зачет не сдал. Теперь нужно присвоить нуль 27-му биту, не трогая остальных. Сначала применим побитовое НЕ к предыдущей константе и получим число, в котором все биты, кроме 27-го, равны 1:

~(1<<27);

Теперь побитово умножим (И) эту константу на quiz1 и получим нужный результат: 0 в 27-м бите и неизменные значения остальных.

quiz1 &= ~(1<<27);

Как проверить значение того же 27-го бита? Побитовое И дает true, если 27-й бит равен 1, и false, если 0:

bool hasPassed = quiz1 & (1<<27);

 

При использовании побитовых операций подобным образом очень легко допустить ошибку. Поэтому чаще всего такие операции инкапсулируются в макросы препроцессора или встроенные функции:

inline boo1 bit_on (unsigned int ui, int pos)

{

return u1 & (1 << pos);

}

Упражнение 1

Даны два целых числа:

unsigned int ui1 = 3, ui2 = 7;

Каков результат следующих выражений?

(a) ui1 & ui2 (c) uil | ui2

(b) ui1 && ui2 (d) uil || ui2

Упражнение 2

Используя пример функции bit_on(), создайте функции bit_turn_on() (выставляет бит в 1), bit_turn_off() (сбрасывает бит в 0), flip_bit() (меняет значение на противоположное) и bit_off() (возвращает true, если бит равен 0). Напишите программу, использующую ваши функции.

Упражнение 3

В чем недостаток функций из предыдущего упражнения, использующих тип unsigned int? Их реализацию можно улучшить, используя определение типа с помощью typedef. Перепишите функцию bit_on(),применив сначала typedef, а затем механизм шаблонов.

 

Класс bitset

Операция	Значение	Использование
test(pos)	Бит pos равен 1?	a.test(4)
any()	Хотя бы один бит равен 1?	a.any()
none()	Ни один бит не равен 1?	a.none()
count()	Количество битов, равных 1	a.count()
size()	Общее количество битов	a.size()
[pos]	Доступ к биту pos	a[4]
flip()	Изменить значения всех	a.flip()
flip(pos)	Изменить значение бита pos a.fli	p(4)
set()	Выставить все биты в 1	a.set()
set(pos)	Выставить бит pos в 1 a.se	t(4)
reset()	Выставить все биты в 0	a.reset()
reset(pos)	Выставить бит pos в 0 a.rese	t(4)

 

Необходимость создавать сложные выражения для манипуляции битовыми векторами затрудняет использование встроенных типов данных. Класс bitset упрощает работу с битовым вектором. Вот какое выражение нам приходилось писать в предыдущем разделе для того, чтобы “взвести” 27-й бит:

quiz1 |= 1<<27;

При использовании bitset то же самое мы можем сделать двумя способами:

quiz1[27] = 1;

или

quiz1.set(27);

(В нашем примере мы не используем нулевой бит, чтобы сохранить “естественную” нумерацию. На самом деле, нумерация битов начинается с 0.)

Для использования класса bitset необходимо включить заголовочный файл:

#include <bitset>

Объект типа bitset может быть объявлен тремя способами.

Способ 1. В определении по умолчанию мы просто указываем размер битового вектора:

bitset<32> bitvec;

Это определение задает объект bitset, содержащий 32 бита с номерами от 0 до 31. Все биты инициализируются нулем.

С помощью функции any() можно проверить, есть ли в векторе единичные биты. Эта функция возвращает true, если хотя бы один бит отличен от нуля. Например:

bool is_set = bitvec.any();

Переменная is_set получит значение false, так как объект bitset по умолчанию инициализируется нулями.

Парная функция none() возвращает true, если все биты равны нулю:

sbool is_not_set = bitvec.none();

Изменить значение отдельного бита можно двумя способами: воспользовавшись функциями set() и reset() или индексом.

Так, следующий цикл выставляет в 1 каждый четный бит:

for (int index=0; index<32; ++index)

if (index % 2 == 0)

bitvec[ index ] = 1;

 

Аналогично существует два способа проверки значений каждого бита – с помощью функции test() и с помощью индекса. Функция test () возвращает true, если соответствующий бит равен 1, и false в противном случае. Например:

if (bitvec.test(0))

// присваивание bitvec[0]=1 сработало!;

 

Значения битов с помощью индекса проверяются таким образом:

cout << "bitvec: включенные биты:\n\t";

for (int index = 0; index < 32; ++-index)

if (bitvec[ index ])

cout << index << " ";

cout << endl;

 

Следующая пара операторов демонстрирует сброс первого бита двумя способами:

bitvec.reset(0);

bitvec[0] = 0;

 

Функции set() и reset() могут применяться ко всему битовому вектору в целом. В этом случае они должны быть вызваны без параметра. Например:

// сброс всех битов

bitvec.reset();

if (bitvec.none()!= true)

// что-то не сработало

// установить в 1 все биты вектора bitvec

if (bitvec.any()!= true)

// что-то опять не сработало

 

Функция flip() меняет значение отдельного бита или всего битового вектора:

bitvec.f1ip(0); // меняет значение первого бита

bitvec[0].flip(); // тоже меняет значение первого бита

bitvec.flip(); // меняет значения всех битов

 

Существуют еще два способа определить объект типа bitset. Оба они дают возможность проинициализировать объект определенным набором нулей и единиц. Первый способ – явно задать целое беззнаковое число как аргумент конструктору. Начальные N позиций битового вектора получат значения соответствующих двоичных разрядов аргумента. Например:

bitset< 32 > bitvec2(Oxffff);

инициализирует bitvec2 следующим набором значений:

В результате определения

bitset< 32 > bitvec3(012);

у bitvec3 окажутся ненулевыми биты на местах 1 и 3:

В качестве аргумента конструктору может быть передано и строковое значение, состоящее из нулей и единиц. Например, следующее определение инициализирует bitvec4 тем же набором значений, что и bitvec3:

// эквивалентно bitvec3

string bitva1("1010");

bitset< 32 > bitvec4(bitval);

Можно также указать диапазон символов строки, выступающих как начальные значения для битового вектора. Например:

// подстрока с шестой позиции длиной 4: 1010

string bitval ("1111110101100011010101");

bitset< 32 > bitvec5(bitval, 6, 4);

Мы получаем то же значение, что и для bitvec3 и bitvec4. Если опустить третий параметр, подстрока берется до конца исходной строки:

// подстрока с шестой позиции до конца строки: 1010101

string bitva1("1111110101100011010101");

bitset< 32 > bitvec6(bitval, 6);

 

Класс bitset предоставляет две функции-члена для преобразования объекта bitset в другой тип. Для трансформации в строку, состоящую из символов нулей и единиц, служит функция to_string():

string bitva1(bitvec3.to_string());

Вторая функция, to_long(), преобразует битовый вектор в его целочисленное представление в виде unsigned long, если, конечно, оно помещается в unsigned long. Это видоизменение особенно полезно, если мы хотим передать битовый вектор функции на С или С++, не пользующейся стандартной библиотекой.

К объектам типа bitset можно применять побитовые операции. Например:

bitset<32> bitvec7 = bitvec2 & bitvec3;

Объект bitvec7 инициализируется результатом побитового И двух битовых векторов bitvec2 и bitvec3.

bitset<32> bitvec8 = bitvec2 | bitvec3;

Здесь bitvec8 инициализируется результатом побитового ИЛИ векторов bitvec2 и bitvec3. Точно так же поддерживаются и составные операции присваивания и сдвига.

Упражнение 4

Допущены ли ошибки в приведенных определениях битовых векторов?

(a) bitset<64> bitvec(32);

(b) bitset<32> bv(1010101);

(c) string bstr; cin >> bstr; bitset<8>bv(bstr);

(d) bitset<32> bv; bitset<16> bvl6(bv);

Упражнение 5

Допущены ли ошибки в следующих операциях с битовыми векторами?

extern void bitstring(const char*);

bool bit_on (unsigned long, int);

bitset<32> bitvec;

(a) bitsting(bitvec.to_string().c_str());

(b) if (bit_on(bitvec.to_1ong(), 64))...

(c) bitvec.f1ip(bitvec.count());

Упражнение 6

Дана последовательность: 1,2,3,5,8,13,21. Каким образом можно инициализировать объект bitset<32> для ее представления? Как присвоить значения для представления этой последовательности пустому битовому вектору? Напишите вариант инициализации и вариант с присваиванием значения каждому биту.

 

 

Указатели в C++

 

При выполнении любой программы, все необходимые для ее работы данные должны быть загружены в оперативную память компьютера. Для обращения к переменным, находящимся в памяти, используются специальные адреса, которые записываются в шестнадцатеричном виде, например 0x100 или 0x200.

Если переменных в памяти потребуется слишком большое количество, которое не сможет вместить в себя сама аппаратная часть, произойдет перегрузка системы или её зависание.

Если мы объявляем переменные статично, то они остаются в памяти до того момента, как программа завершит свою работу, а после чего уничтожаются.

Такой подход может быть приемлем в простых примерах и несложных программах, которые не требуют большого количества ресурсов. Если же наш проект является огромным программным комплексом с высоким функционалом, объявлять таким образом переменные, естественно, было бы довольно не умно.

Можете себе представить, если бы небезызвестная Battlefield 3 использовала такой метод работы с данными? В таком случае, самым заядлым геймерам пришлось бы перезагружать свои высоконагруженные системы кнопкой reset после нескольких секунд работы игры.

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

Естественно, все это занимает какое-то место в оперативной памяти компьютера. Если не уничтожать неиспользуемые объекты, очень скоро они заполнят весь объем ресурсов ПК.

По этим причинам, в большинстве языков, в том числе и C/C++, имеется понятие указателя.

Указатель — это переменная, хранящая в себе адрес ячейки оперативной памяти, например 0x100.

Мы можем обращаться, например к массиву данных через указатель, который будет содержать адрес начала диапазона ячеек памяти, хранящих этот массив.

После того, как этот массив станет не нужен для выполнения остальной части программы, мы просто освободим память по адресу этого указателя, и она вновь станет доступно для других переменных.

Ниже приведен конкретный пример обращения к переменным через указатель и напрямую.

Пример использования статических переменных

#include <iostream>using namespace std; int main(){ int a; // Объявление статической переменной int b = 5; // Инициализация статической переменной b a = 10; b = a + b; cout << "b is " << b << endl; return 0;}

 

Пример использования динамических переменных

#include <iostream>using namespace std; int main(){ int *a = new int; // Объявление указателя для переменной типа int int *b = new int(5); // Инициализация указателя *a = 10; *b = *a + *b; cout << "b is " << *b << endl; delete b; delete a; return 0;}

Синтаксис первого примера вам уже должен быть знаком. Мы объявляем/инициализируем статичные переменные a и b, после чего выполняем различные операции напрямую с ними.

Во втором примере мы оперируем динамическими переменными посредством указателей. Рассмотрим общий синтаксис указателей в C++.

Выделение памяти осуществляется с помощью оператора new и имеет вид:

тип_данных *имя_указателя = new тип_данных;

например int *a = new int;. После удачного выполнения такой операции, в оперативной памяти компьютера происходит выделение диапазона ячеек, необходимого для хранения переменной типа int.

Логично предположить, что для разных типов данных выделяется разное количество памяти. Следует быть особенно осторожным при работе с памятью, потому что именно ошибки программы, вызванные утечкой памяти, являются одними из самых трудно находимых. На отладку программы в поисках одной ничтожной ошибки, может уйти час, день, неделя, в зависимости от упорности разработчика и объема кода.

Инициализация значения, находящегося по адресу указателя выполняется схожим образом, только в конце ставятся круглые скобки с нужным значением:

тип данных *имя_указателя = new тип_данных(значение).

В нашем примере это int *b = new int(5).

 

Для того, чтобы получить адрес в памяти, на который ссылается указатель, используется имя переменной-указателя с префиксом &. перед ним (не путать со знаком ссылки в C++ ).

Например, чтобы вывести на экран адрес ячейки памяти, на который ссылается указатель b во втором примере, мы пишем

cout << "Address of b is " << &b << endl;

В моей системе, я получил значение 0x1aba030. У вас оно может быть другим, потому что адреса в оперативной памяти распределяются таким образом, чтобы максимально уменьшить фрагментацию. Поскольку, в любой системе список запущенных процессов, а также объем и разрядность памяти могут отличаться, система сама распределяет данные для обеспечения минимальной фрагментации.

 

Для того, чтобы получить значение, которое находится по адресу, на который ссылается указатель, используется префикс *. Данная операция называется разыменованием указателя.

Во втором примере мы выводим на экран значение, которое находится в ячейке памяти (у меня это 0x1aba030):

cout << "b is " << *b << endl;

В этом случае необходимо использовать знак *.

Чтобы изменить значение, находящееся по адресу, на который ссылается указатель, нужно также использовать звездочку, например, как во втором примере — *b = *a + *b;.

· Когда мы оперируем данными, то используем знак *

· Когда мы оперируем адресами, то используем знак &

В этих вещах очень часто возникают недопонимания, и кстати, не только у новичков. Многие из тех, кто начинал программировать с того же php, также часто испытывают подобную путаницу при работе с памятью.

 

Для того, чтобы освободить память, выделенную оператором new, используется оператор delete.

Пример освобождения памяти

#include <iostream>using namespace std; int main(){ // Выделение памяти int *a = new int; int *b = new int; float *c = new float; //... Любые действия программы // Освобождение выделенной памяти delete c; delete b; delete a; return 0;}

При использовании оператора delete для указателя, знак * не используется.

 

Пример

#include <stdio.h>

#include <math.h>

#include <stdlib.h>

#include <conio.h>

main()

{

int *x=new int;

printf ("x=");

scanf("%d",x);

// ввод данных в десятичном виде

for(int i=sizeof(int)*8-1; i>=0; --i){

printf("%d", *x&(1<<i)?1:0);}

// ввод данных в двоичном виде

char bit;

int *y=new int(0); printf("\n");

for(int i=sizeof(int)*8-1; i>=0; --i){

printf("%d", *y&(1<<i)?1:0);}

printf("\n Vvod in rows 8 bit:\n");

for(int i=sizeof(int)*8-1; i>=0; --i){

bit=getch();printf("%c",bit);

if (bit=='1') *y^=(1<<i); }

printf("\ny=%d\n",*y);

//инверсия

printf ("Input of number bit=");

{int i;

scanf("%d",&i);

if (*y&(1<<i)) *y&=(~(1<<i)); else *y^=(1<<i);

}

for(int i=sizeof(int)*8-1; i>=0; --i){

printf("%d", *y&(1<<i)?1:0);}

printf("\n");

 

delete x,y;

system("pause");

}

12	Поделиться:

Воспользуйтесь поиском по сайту: