Поразрядные операции и операции сдвига над целочисленными данными

 

Целочисленные данные можно подвергать операции сдвига как влево (знак операции – <<), так и вправо (знак операции – >>) на заданное количество двоичных разрядов:

y=x<<3; // сдвиг влево на три двоичные разряда

z=y>>5; // сдвиг вправо на пять двоичных разрядов

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

#include <stdio.h>

#include <conio.h>

int main()

{

int x=5, y=-5;

unsigned z=0xFFFFFFFB;

printf("x=%x y=%x z=%x",x,y,z);

printf("\nx<<2=%x x>>2=%x",x<<2,x>>2);

printf("\ny<<2=%x y>>2=%x",y<<2,y>>2);

printf("\nz<<2=%x z>>2=%x",z<<2,z>>2);

getch();

return 0;

}

//=== Результат работы ===

x=5 y=fffffffb z=fffffffb

x<<2=14 x>>2=1

y<<2=ffffffec y>>2=fffffffe

z<<2=ffffffec z>>2=3ffffffe

Дело в том, что для чисел со знаком операция сдвига на n разрядов эквивалентна умножению на 2ⁿ при сдвиге влево или делению на 2ⁿ при сдвиге вправо. Поэтому для отрицательного операнда результат сдвига должен остаться отрицательным. С этой целью при сдвиге вправо производится размножение знакового разряда.

 

Билет 21а

Имена массивов в качестве указателей. Приведенный индекс в двумерных массивах. Почему в Си отказались от функций Low и High?

Если целочисленному указателю p1 присваивается имя массива a или его адрес, то это эквивалентно засылке в p1 адреса первого элемента массива a[0]:

int a[10];

int *p1=a; //p1 смотрит на начало массива a

int *p2=&a[0]; //p2 тоже смотрит на начало массивa a

int *p3=(int *)&a; //p3 тоже смотрит на начало массивa a

Когда указатель p1 "смотрит" на переменную x, то по значению указателя можно извлечь значение переменной x или изменить его:

int x=5,y;

int *p1=&x; //значением p1 является адрес x

..........

y=*p1; //теперь значение переменной y равно 5

*p1=2; //теперь значение переменной x равно 2

Когда указатель p2 "смотрит" на начало массива q, то доступ к элементам этого массива можно организовать одним из следующих способов:

int q[20];

int *p2=q;

...........

y=*(p2+5); //теперь y=q[5]

x=p2[3]; //теперь x=q[3]

*(p2+1)=7; //теперь q[1]=7

Основные операции, чаще всего применяемые к указателям – сложение указателя с целым числом или вычитание из указателя целого числа. Обе они широко применяются в том случае, когда указатель связан с массивом. По сути дела, эти операции эквивалентны аналогичным процедурам над индексами элементов массива. И точно так же как прибавление к индексу означает переход к следующему элементу массива, прибавление 1 к указателю означает увеличение его текущего значения на количество байт, соответствующих типу указателя (точнее, типу данных, на которые указатель обязан смотреть):

int q[6]={1,2,3,4,5,6};

int *p = &q[3];

cout << *p++ <<endl; //сначала выводится 4, потом p=&q[4]

cout << (*p)++ <<endl; //сначала выводится 5, потом p=&q[5]

cout << *(p++) <<endl; //сначала выводится 6, потом p=&q[6]

Если при обработке некоторого массива используются два указателя p1 и p2, продвигаемые навстречу друг другу, то их разность (p2-p1) определяет количество элементов массива расположенных между этим двумя адресами.

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

Пример 9.10. Формирование единичной матрицы с приведенными индексами.

#include <stdio.h>

#include <math.h>

#include <conio.h>

void eye(int *a, int n)

{ int i,j;

for(i=0; i<n; i++)

for(j=0; j<n;j++)

{ if(i==j) a[i*n+j]=1;

else a[i*n+j]=0;

}

}

void main()

{ int i,j,v[5][5];

eye((int*)v,5);

for(i=0;i<5;i++)

{ for(j=0;j<5;j++)

printf("%3d",v[i][j]);

printf("\n");

}

getch();

}

Массив указателей p на строки двумерного массива v может быть сформирован и другими способами:

int *p[4]={(int *)v,(int *)(v+1),(int *)(v+2),(int *)(v+3)};

int *p[4]={v[0],v[1],v[2],v[3]};

int *p[4]={*v,*(v+1),*(v+2),*(v+3)};

Очевидно, что указатель p[0] "смотрит" на элемент v[0][0]. Поэтому указатель p[0][1]=p[0]+1 "смотрит" на элемент v[0][1], указатель p[0][2] – на элемент v[0][2] и т.д. Можно было бы видоизменить заголовок функции transp следующим образом:

void transp(int **p,int n)

Все эти модификации ничего не меняют в алгоритмах работы программ.

 

Функции Low и High

 

При работе с массивами вам часто придется пользоваться функциями Low и High. Как я уже говорил, массив может быть объявлен с произвольными нижней и верхней границами. Функция low возвращает нижнюю границу массива, а функция High — его верхнюю границу

 

 

1.6.2. Отличия языка C++ от Паскаля

Как показывает практика, язык С++ удобно изучать вторым - после Паскаля. Во-первых, Паскаль - более дисциплинирующий язык, в нем сложно создать неоднозначные конструкции. Во-вторых, в С++, в силу особенностей синтаксиса, довольно рано приходится разбираться в ссылках и указателях, а эти темы бывают сложны для студентов.

 

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

 

Для облегчения перехода от Паскаля к С++ вкратце перечислю основные отличия этих языков.

 

1. Компилятор Паскаля однопроходный.

 

Компилятор С++ двухпроходный. Первый проход его принято называть препроцессором, он формирует окончательную структуру текста программы и обрабатывает собственные директивы (в коде они начинаются символом "#"), например:

#define MAX(a,b) ((a)>(b))?(a):(b)

#include <stdio.h>

 

 

Подробнее о директивах препроцессора см. соответствующий раздел.

 

В силу наличия препроцессора компилятор языка С++ работает значительно медленнее аналогичного компилятора Паскаля.

 

2. Стандарт Паскаля - блочный язык. В Turbo (Borland) Pascal используются элементы модульности, однако подпрограммы по-прежнему могут вкладываться друг в друга.

 

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

 

3. Для описания внешнего интерфейса (то есть доступных элементов) модуля в Паскале используется раздел interface. При помощи этого раздела модули Паскаля в составе проекта связываются между собой.

 

Для связи файлов программы в С++ используются так называемые заголовочные файлы (хидеры, headers) "*.h". Обычно они содержат внутри себя объявления переменных и функций, использующихся в соответствующем файле программы, в том числе внешних.

 

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

 

Обратите внимание: интерфейс модуля в Паскале содержит элементы, которые будут доступны вне модуля. Хидер в С++ содержит элементы любых модулей, которые будет использовать файл, подключивший этот хидер.

 

4. Паскаль - язык с нежестким контролем регистра символов. Идентификаторы "MyName", "myname" и "myNAME" в нем считаются одинаковыми.

 

Синтаксис С++ учитывает регистр символов. Возможно, это дает программисту некоторые преимущества, однако чаще мы сталкиваемся с затруднениями:

Велика вероятность опечататься при наборе идентификатора, а это приведет к ошибке на стадии компиляции. Например, в программе есть переменная "Len", а в одном месте она введена, как "len".

Если в системе объявлены переменные, отличающиеся только регистром символов, то случайная опечатка при наборе приведет к возникновению семантической (смысловой) ошибки на стадии выполнения. Поэтому не стоит называть разные переменные одной программы именами "Len", "len" и "LEN", хотя компилятор и будет считать их различными.

 

Чувствительность к регистру заимствуют и все производные от С языки: PHP, ActionScript, JavaScript и др.

 

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

 

С++, по сравнению с Паскалем, имеет гораздо более свободный синтаксис выражений. Однако, проблема заключается в том, что логические ошибки в структуре выражений часто приводят не к синтаксическим, а к семантическим ошибкам. Последние же, как известно, намного сложнее в отладке.

 

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

 

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

 

В производных от С языках понятие процедуры также отсутствует.

 

7. В Паскале существуют отдельные строковый и логический типы, Значения типа char в нем - символы.

 

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

 

8. В Паскале переменные, константы, типы объявляются строго в соответствующих разделах описания: var, const, type. Эти разделы располагаются до начала реализации подпрограммы или программы.

 

В С++ переменные, константы, типы можно объявлять в любом месте программы.

Главное отличие между языками Си и Паскаль состоит в том, что

Паскаль выполняет гораздо больше строгих проверок. Эти проверки

гарантируют: что при вызове передается правильное количество и

типы параметров; что значения функции используются способом, со-

ответствующим их типу и т.д. Таким образом, в отличие от языка

Си, в языке Паскаль программа должна быть объявлена либо процеду-

рой (подпрограмма, которая не возвращает значения), либо функци-

ей.

Язык Паскаль также обеспечивает использование автоматических

переменных для памяти локальных данных. Как и в языке Си, в языке

 

Паскаль нет стандартных решений о назначении порядка локальных

переменных в стеке. Также, как и в языке Си, в Паскале память для

локальных переменных распределяется при вершине стека на входе в

вызываемую программу. Если процедура MyProc использует локальные

переменные LocIndx, LocChar и LocWord, то они должны будут ссы-

латься так, как показано в структуре StackFrame листинга 2-8.

Паскаль эквивалентен программе, похожей на ниже приведенную:

 

procedure MyProc (Param1, Param2, Param3: integer);

var

LocIndx, LocWord: integer;

LocChar [1..14]: character;

begin

...

 

Из листинга 2-4 можно увидеть, что в отличие от языка Си,

язык Паскаль помещает свои аргументы в порядке, в котором они

объявляются, слева направо. Причина, по которой этот способ воз-

можен, состоит в том, что компилятор языка Паскаль гарантирует,

что все обращения, выдаваемые программой, обеспечивают правильное

количество и типы аргументов. Язык Паскаль просто не позволяет

передавать переменное количество параметров, поэтому порядок пе-

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

Следствием строгой проверки вызова, выполняемой языком Пас-

каль, является то, что вызываемая программа всегда получает одно

и то же количество аргументов, позволяющее вызываемой программе

использовать инструкцию RET N для очистки стека, нежели зависеть

от вызывающей программы.

Другим сходством с языком Си является то, что язык Паскаль

обычно передает свои переменные по значению, однако, если требу-

ется, то переменные можно передавать по адресу, используя описа-

ние var (переменная).

 

8.10. Указатели на функцию и передача их в качестве параметров

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

Одним из таких примеров является функция вычисления определенного интеграла – кроме параметров-значений, задающих пределы интегрирования, ей необходимо сообщить имя подпрограммы, вычисляющей значения подынтегральной функции. В такой ситуации обычно используют указатель на функцию.

Объявление указателя pf на функцию f(x), аргумент которой и возвращаемое значение имеют тип double, выглядит следующим образом:

double (*pf)(double x);

Оно напоминает прототип функции, в котором имя функции заменено именем указателя, заключенным в круглые скобки.

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

double int_rect(double a, double b, double (*f)(double x))

{ int i, n=100;

double s=0,h=(b-a)/n;

for(i=0; i<=n; i++) s += f(a+i*h);

return s*h;

}

Последним аргументом процедуры int_rect является указатель на функцию. Поэтому в качестве фактического параметра мы должны подставить имя подынтегральной функции. Таковым, в частности, может быть имя любой стандартной функции из библиотеки math.h:

cout << int_rect(0,M_PI, sin) << endl; //результат= 1.99984

cout << int_rect(0,M_PI, cos) << endl; //результат=-4.18544e-17

В качестве второго примера рассмотрим программу нахождения корня уравнения y=f(x), если известно, что на интервале [x1, x2] эта функция меняет знак. Алгоритм базируется на делении отрезка пополам. В точке xmid=(x1+x2)/2 смотрим знак функции f, который совпадет либо со знаком f(x1), либо со знаком f(x2). Выбираем ту половину отрезка, на концах которой функция принимает разные знаки. Затем исследуем его середину и т.д. Как только длина очередного отрезка станет достаточно малой или значение функции в центре отрезка окажется меньше заданной точности, процесс поиска корня прекращается.

#include <iostream.h>

#include <conio.h>

#include <math.h>

double y(double x) //функция f(x)=x²-4

{ return x*x-4; }

double root(double x1,double x2,double eps, double(*f)(double x))

{ double f12,f1,f2,xmid;

f1= f (x1); f2= f (x2);

if(f1*f2>0)

{ cerr<<"Error: sign(f1)=sign(f2)"; getch(); exit(0); }

while(x2-x1 > eps)

{ xmid=(x1+x2)/2.;

f12= f (xmid);

if(fabs(f12) < eps)

return xmid;

if(f12*f1>0) { x1=xmid; f1=f12; }

else {x2=xmid; f2=f12; }

}

return (x1+x2)/2.;

}void main()

{ cout<<root(0,10,1e-4, y);

getch();

}

//=== Результат работы ===

2.00001