Задачи 159-166. Побитовые операторы

159. Напишите функцию int bitcount(unsigned x), возвращающую число единиц в двоичном представлении величины x. Указание. Создайте величину onebit, имеющую единичку в младшем правом разряде. В цикле сравнивайте побитово x с onebit и сдвигайте onebit на 1 влево, пока onebit не станет 0.

160. Напишите программу, подсчитывающую число двоичных разрядов, отводимых под данные типа char, int, short, long, unsigned.

161. Напишите функцию setbits(x, p, n, y), возвращающую значение x, в котором n бит, начиная с p-ой позиции справа, заменены на n правых разрядов из y (остальные биты не меняются).

162. Напишите функцию invert(x, p, n), возвращающую значение x с инвертированными n битами, начиная с позиции p (остальные биты не изменяются).

163. Напишите функцию, которая циклически сдвигает влево x на 1 позицию. При этом старший разряд x ставится на место младшего.

164. Напишите функцию leftrot(x, n), которая циклически сдвигает влево x на n разрядов.

165. Напишите функцию rightrot(x, n), которая циклически сдвигает вправо x на n позиций.

166. Применительно к числам, в представлении которых использован дополнительный код, выражение x &= (x-1)уничтожает самую правую 1 в x. Объясните почему. Используйте это наблюдение для более быстрого варианта функции bitcount, подсчитывающей число единиц в двоичном представлении своего аргумента.

 

Глава 14. Структуры, перечисления, объединения

Объявление структур

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

Для моделирования точек на плоскости, рис.34, можно использовать следующую структуру:

struct point{ // Структура для моделирования точек на плоскости

int x;

int y;

};

Рис.34. Точки на плоскости

Здесь struct – это ключевое слово, с которого начинается описание структуры. Идентификатор point – это имя структуры. В фигурных скобках помещается список объявлений членов или полей структуры x и y. Имена членов структуры должны различаться, но могут совпадать с именами других переменных программы.

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

point pt1, pt2, pt3; // Определение трех точек на плоскости

Эта запись аналогична объявлению переменных встроенных типов:

int a, b, c;

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

Структурные переменные можно инициализировать при определении, например,

point nachkoord = {0, 0}, p1 = {1, 1};

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

Доступ к члену структуры осуществляется конструкцией:

ИМЯ_СТРУКТУРЫ.ЧЛЕН

Например, чтобы напечатать координаты точки p1, можно использовать инструкцию:

cout << p1.x <<”, ” << p1.y;

Рис.35. Прямоугольник как совокупность двух точек

Структуры могут быть вложенными друг в друга, например, прямоугольник, рис.35, можно рассматривать как совокупность двух точек, объединенных в одну структуру:

struct rect{ // Прямоугольник

point pt1; // Первая вершина

point pt2; // Вторая вершина

};

Структура rect имеет своими членами две структуры point.

Пусть объявлена структурная переменная:

rect screen;

Выражение screen.pt1.x ссылается на координату x точки pt1 из структуры screen.

Структуры и функции

Рассмотрим несколько функций, манипулирующих точками и прямоугольниками.

// make_point: создание точки

point make_point(int x, int y)

{

point tmp;

tmp.x = x; tmp.y = y;

return tmp;

}

Здесь внутри функции создается локальная структура tmp, ее членам присваиваются значения. Затем с помощью return значение структуры возвращается из функции, после чего работа функции завершается, и локальная структура tmp уничтожается. Значение структуры, возвращенное из функции, может быть присвоено какой-то структурной переменной в вызывающей программе.

Следующая функция создает прямоугольник по двум точкам p и q:

// make_rect: создание прямоугольника

rect make_rect(point p, point q)

{

rect tmp;

tmp.pt1 = p; tmp.pt2 = q;

return tmp;

}

Здесь внутри функции создается локальная структура tmp, полям которой присваиваются значения структур p и q. При присваивании структур производится почленное копирование.

Возможно, что точка pt1 не лежит ниже и левее, чем pt2. Следующая функция преобразует прямоугольник к каноническому виду.

#define max(a, b) (a)>(b)?(a):(b) // Макрос для выбора максимума

#define min(a, b) (a)<(b)?(a):(b) // Макрос для выбора минимума

// canon_rect: канонизация координат прямоугольника

rect canon_rect(rect r)

{

rect tmp;

tmp.pt1.x = min(r.pt1.x, r.pt2.x);

tmp.pt1.y = min(r.pt1.y, r.pt2.y);

tmp.pt2.x = max(r.pt1.x, r.pt2.x);

tmp.pt2.y = max(r.pt1.y, r.pt2.y);

return tmp;

}

Указатели на структуры

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

Объявление

point* pp;

сообщает, что pp есть указатель на структуру point. Если pp ссылается на структуру, то выражение

*pp

есть сама структура, а выражения

(*pp).x, (*pp).y

являются членами структуры. Скобки в выражении (*pp).x необходимы, так как приоритет оператора точка (.) выше, чем приоритет оператора звездочка (*) и выражение *pp.x будет проинтерпретировано как *(pp.x), что неверно, так как pp не структура, а pp.x не является указателем.

Пусть имеем фрагмент программы:

point origin, *pp; // Структура и указатель на структуру

pp = &origin; // Указателю pp присвоен адрес структуры origin

Напечатать координаты точки origin можно следующим образом:

cout << ”origin: (” << (*pp).x << ”, ” << (*pp).y << ”)”;

Для доступа к членам структуры через указатель существует специальный оператор стрелка, образованный символами минус и больше:

->

Если p – указатель на структуру, то выражение

p->ЧЛЕН_СТРУКТУРЫ

есть ее отдельный член, поэтому напечатать координаты точки origin можно инструкцией:

cout <<”origin: (” << pp->x << ”, ” << pp->y << ”)”;

Операторы точка (.) и стрелка (->) имеют одинаковый приоритет и выполняются слева направо. Пусть, например, сделаны объявления:

rect r, *pr = &r;

Следующие выражения эквивалентны:

r.pt1.x, pr->pt1.x, (r.pt1).x

С помощью функции make_point можно динамически инициализировать структуры. Например, следующая функция получает в качестве аргумента указатель на структуру rect, внутри функции создается точка, динамически инициализируемая вызовом функции.

// cetner_rect: возвращает точку - центр прямоугольника

point center_rect(rect* pr)

{

point tmp =

make_point((pr->pt1.x + pr->pt2.x) / 2, (pr->pt1.y + pr->pt2.y) / 2);

return tmp;

}