Файл: А. Б. Шнейвайс основы программирования.pdf

printf("a : %s\n", a%2==0 ? " четное " : " нечетное"); // Четно ли a?
printf("b : %s\n", b%2==1 ? " нечетное" : "

четное "); // Нечетно ли b?
u=a; v=b; w=2*u; p=(u+v+w)/2;
// Можно ли построить треугольник printf("u=%g v=%g w=%g p=%g
%s\n",
// с длинами сторон u, v и w=2*u u, v, w, p, (u return 0;
}
Результаты двух пропусков этой программы:
Введите a:3
Введите a:4
a=3
a=4
Введите b:4
Введите b:3
b=4
b=3
min(3,4)=3
min(4,3)=3
max(3,4)=4
max(4,3)=4
a :
нечетное a :
четное b :
четное b :
нечетное u=3
v=4
w=6
p=6.5
Можно u=4
v=3
w=8
p=7.5
Нельзя
Тернарная операция позволяет модифицировать программу из пункта
1.2.2 так, чтобы получить результат в более удобочитаемом (как счита- ется в [8]) виде:
19

#include
int main(void)
{ char *ttrue="ИСТИНА", *ffalse="ЛОЖЬ";
float v1, v2;
printf("Введите v1:"); scanf("%f",&v1);
printf("Введите v2:"); scanf("%f",&v2);
printf("%g > %g это %s\n",v1, v2, v1>v2
? ttrue : ffalse);
printf("%g < %g это %s\n",v1, v2, v1? ttrue : ffalse);
printf("%g == %g это %s\n",v1, v2, v1==v2 ? ttrue : ffalse);
printf("%g >= %g это %s\n",v1, v2, v1>=v2 ? ttrue : ffalse);
printf("%g <= %g это %s\n",v1, v2, v1<=v2 ? ttrue : ffalse);
printf("
!%g это %s\n", v1,
!v1
? ttrue : ffalse);
printf("
!%g это %s\n", v2,
!v2
? ttrue : ffalse);
printf("%g || %g это %s\n",v1, v2, v1||v2 ? ttrue : ffalse);
printf("%g && %g это %s\n",v1, v2, v1&&v2 ? ttrue : ffalse);
return 0;
}
Введите v1:1.2
Введите v1:0.0
Введите v1:1.2
Введите v2:0
Введите v2:1.2
Введите v2:1.0 1.2 > 0
это ИСТИНА
0 > 1.2
это ЛОЖЬ
1.2 > 1
это ИСТИНА
1.2 < 0
это ЛОЖЬ
0 < 1.2
это ИСТИНА
1.2 < 1
это ЛОЖЬ
1.2 == 0 это ЛОЖЬ
0 == 1.2 это ЛОЖЬ
1.2 == 1 это ЛОЖЬ
1.2 >= 0 это ИСТИНА
0 >= 1.2 это ЛОЖЬ
1.2 >= 1 это ИСТИНА
1.2 <= 0 это ЛОЖЬ
0 <= 1.2 это ИСТИНА
1.2 <= 1 это ЛОЖЬ
!1.2
это ЛОЖЬ
!0
это ИСТИНА
!1.2
это ЛОЖЬ
!0
это ИСТИНА
!1.2
это ЛОЖЬ
!1
это ЛОЖЬ
1.2 || 0 это ИСТИНА
0 || 1.2 это ИСТИНА
1.2 || 1 это ИСТИНА
1.2 && 0 это ЛОЖЬ
0 && 1.2 это ЛОЖЬ
1.2 && 1 это ИСТИНА
1.2.4
Операция присваивания
Оператор присваивания ФОРТРАНа нацелен только на пересылку значения, выработанного выражением справа от значка оператора при- сваивания = , в переменную, имя которой помещено слева от =.
Операция присваивания СИ (обозначается тем же значком =) не только пересылает значение, но и полагает это переданное значение сво- им результатом. Поэтому в СИ, если выгодно, в одном предложении до- пустима запись сразу нескольких присваиваний:
#include
int main(void)
{ double u,v,w,x,y,z;
u=v=w=x=y=z=1.3l;
printf("u=%g v=%g w=%g x=%g y=%g z=%g\n",u,v,w,x,y,z);
return 0; }
20

Кроме того, в СИ есть комбинированная операция присваивания, в которой запись операции присваивания комбинируется с записью любой из операций
*
/
+
-
%
<<
>>
&
^
|
операции сдвига поразрядная поразрядное поразрядная конъюнкция исключающее дизъюнкция and xor or
Правило записи комбинированной операции присваивания:
v op= выражение;.
Здесь v – имя переменной, а op – одна из указанных операций.
Смысловой эквивалент комбинированной операции :
v=v op выражение;.
Например,
#include
//
Результат работы программы:
int main(void)
//
{double u,v,w,x,y,z;
//
int i=5;
//
u=v=w=x=y=z=1.3;
//
u*=2;
printf("u*=2
=%g\n",u);
//
u=u*2
=2.6
v/=1.3;
printf("v/=1.3 =%g\n",v);
//
v=v/1.3 =1
w+=5;
printf("w+=5
=%g\n",w);
//
w=w+5
=6.3
x-=1.05; printf("x-=1.05=%g\n",x);
//
x=x-1.05=0.25
i%=3;
printf("i%=3
=%d\n",i);
//
i=i%3
=2
return 0;
}
1.2.5
Операция sizeof
Результат операции sizeof – количество байт нужное для размещения значения того или иного типа. Операндом операции sizeof может быть имя типа, имя переменной или выражение.
Если переменная является массивом, то sizeof возвращает число байт,
необходимое для размещения всех элементов массива. Например,
21

#include
using namespace std;
int main(void)
{ int i,r;
char c;
long int k;
double f;
long double ff;
char cc[8]; double ar[10]; long double dr[100];
cout<<"
sizeof(
char
)="<cout<<"
sizeof(
short
)="<cout<<"
sizeof(
int
)="<cout<<"
sizeof( long int )="<cout<<"
sizeof(
float
)="<float )<cout<<"
sizeof(
double
)="<cout<<"
sizeof(long double)="<cout<<"
sizeof( i)="<cout<<"
sizeof( c)="<cout<<"
sizeof( k)="<cout<<"
sizeof( f)="<cout<<"
sizeof(ff)="<cout<<"
sizeof( cc)="<cout<<"
sizeof( ar)="<cout<<"
sizeof( dr)="<cout<<"
sizeof(i+5)="<cout<<"
sizeof(f*f)="<return 0;
}
Результат работы приведенной программы:
sizeof(
char
)=1
sizeof(
short
)=2
sizeof(
int
)=4
sizeof( long int )=4
sizeof(
float
)=4
sizeof(
double
)=8
sizeof(long double)=12
sizeof( i)=4
sizeof( c)=1
sizeof( k)=4
sizeof( f)=8
sizeof(ff)=8
sizeof( cc)=8
sizeof( ar)=80
sizeof( dr)=1200
sizeof(i+5)=4
sizeof(f*f)=8 22

В современном ФОРТРАНе имеется несколько встроенных функций,
родственных СИ-операции sizeof. В ФОРТРАНе-95 это — функции kind и size.
Встроенная ФОРТРАН-функция kind(x) возвращает параметр раз- новидности объекта (константы, переменной и т.д) того или иного типа,
то есть количество байт нужное для размещения одного его значения .
Например,
program testkind; implicit none integer(1)
i; integer(2) j; integer(4) k; integer(8) m character(33) c complex q; complex*8 r; complex(8) rr; complex*16 r2; real a, aa(5)
real*8 b write(*,*) kind(i),’ ’, kind(j),’ ’, kind(k ),’ ’, kind( m )
write(*,*) kind(a),’ ’, kind(b),’ ’, kind(aa),’ ’, kind(3.4)
write(*,*) kind(c),’ ’, kind(1+r2),’ ’,kind(sin(7.0)),’ ’, kind(8.3d0)
write(*,*) kind(q),’ ’, kind(r),’ ’, kind(r2),’ ’,kind(rr)
end
Результат ее работы
1 2
4 8
4 8
4 4
1 8
4 8
4 4
8 8
1. Аргумент у ФОРТРАН-функции kind не может быть именем типа
(как могло быть в случае СИ-операции sizeof).
2. Кроме того, когда аргумент kind – имя массива, то результат рабо- ты – размер в байтах одного элемента, а не всего массива.
3. В старых версиях ФОРТРАНа количество байт, отводимое под зна- чение типа real, указывалось при её описании после слова real через символ * (звёздочка) — real*8. Такой способ возможен и в современ- ном ФОРТРАНе, хотя рекомендуется использовать круглые скоб- ки — real(8). Однако, если при описании объекта типа complex*8
восьмёрка указывает полную длину значения типа complex (т.е. 4
байта на вещественную часть и четыре байта на мнимую), то описа- ние complex(8) указывает количество байт отводимое под каждый компонент (т.е. восемь байт под вещественную и восемь под мни- мую). Именно поэтому программе testkind значение kind(r)=4,
но значение kind(rr)=8.
23

Встроенная ФОРТРАН-функция size(array) определяет размер мас- сива, т.е.полное число элементов массива array.
Полный синтаксис вызова result=size(array[,dim[,kind]])
(здесь квадратные скобки — не элемент синтаксиса ФОРТРАНа, а ука- зание, что помещённый внутри их фрагмент необязателен). Если при вызове size помимо array указан ещё и аргумент dim, то в качестве результата будет возвращено число элементов массива array по указан- ному в dim номеру измерения массива, т.е. длина экстента массива по измерению dim. При наличии kind третьего аргумента результат, най- денный size, будет приведён к integer-типу, указанному в kind. Напри- мер,
program testsize; implicit none; real a(2,3,4,5)
write(*,*) ’size( a )=’,size( a )
write(*,*) ’size(a,1)=’,size(a,1); write(*,*) ’size(a,2)=’,size(a,2)
write(*,*) ’size(a,3)=’,size(a,3); write(*,*) ’size(a,4)=’,size(a,4)
write(*,*) ’size( a(2,:,:,:) )=’,size( a(2,:,:,:) )
write(*,*) ’size( a(:,3,:,:) )=’,size( a(:,3,:,:) )
write(*,*) ’size( a(:,:,4,:) )=’,size( a(:,:,4,:) )
write(*,*) ’size( a(:,:,:,5) )=’,size( a(:,:,:,5) )
write(*,*) ’size( a(2,3,:,:) )=’,size( a(2,3,:,:) )
write(*,*) ’size( a(2,3,4,:) )=’,size( a(2,3,4,:) )
write(*,*) ’size( a(2,3,:,5) )=’,size( a(2,3,:,5) )
end
Результат ее работы size( a )=
120
size(a,1)=
2
size(a,2)=
3
size(a,3)=
4
size(a,4)=
5
size( a(2,:,:,:) )=
60
size( a(:,3,:,:) )=
40
size( a(:,:,4,:) )=
30
size( a(:,:,:,5) )=
24
size( a(2,3,:,:) )=
20
size( a(2,3,4,:) )=
5
size( a(2,3,:,5) )=
4 24

В GNU-расширении ФОРТРАНа 2003 имеется встроенная функция sizeof(x), которая, как и CИ-шная sizeof, вычисляет число байт памяти,
необходимой для хранения значения аргумента x.
program test_sizeof; implicit none real f4; real(8) f; real(16) ff; integer i complex*8 c4; complex(8) c8
character cc(8); real(8) ar(10); real(16) dr(100)
write(*,*) ’sizeof( f4)=’,sizeof(f4); write(*,*) ’sizeof(
f)=’,sizeof( f)
write(*,*) ’sizeof( ff)=’,sizeof(ff); write(*,*) ’sizeof( cc)=’,sizeof(cc)
write(*,*) ’sizeof( ar)=’,sizeof(ar); write(*,*) ’sizeof(i+5)=’,sizeof(i+5)
write(*,*) ’sizeof(f*f)=’,sizeof(f*f)
write(*,*) ’sizeof( c4)=’,sizeof(c4);
write(*,*) ’sizeof( c8)=’,sizeof(c8)
end program test_sizeof sizeof( f4)=
4
!
Результат работы test_sizeof sizeof(
f)=
8
! ==============================
sizeof( ff)=
16
sizeof( cc)=
8
sizeof( ar)=
80
sizeof(i+5)=
4
sizeof(f*f)=
8
sizeof( c4)=
8
sizeof( c8)=
16
Результат работы sizeof(x), зависит от разновидности типа аргумента.
В ФОРТРАНе и СИ описатели разновидностей типа и обозначаются по разному, и, более того, количество этих разновидностей различно.
Поэтому, если в gfortran-сборке исполнимого файла участвуют объ- ектные файлы функций, написанных на СИ (т.е. полученных gcc/g++- компилятором), то в исходном ФОРТРАН-тексте важно правильно ука- зать требуемый тип разновидности аргумента СИ-функции.
Современный ФОРТРАН использует для этого встроенный модуль
ISO C BINDING (International Standard Organization — привязка ISO
С), в котором определены некоторые функции (в частности, и С_sizeof)
и установлено соответствие ФОРТРАН- и СИ-типов посредством соот- ветствующих именованных констант.
Подробнее об ISO C BINDING, о совмещённом (или интеропера- бельном) программировании мы немного узнаем в третьем семестре. Бо- лее строгое изложение вопроса будет дано в четвёртом.
25

1.2.6
Операции сдвига
СИ:
Сдвиг влево операнда, указанного слева от знака операции, на число двоичных разрядов,указанных справа.
Сдвиг вправо операнда, указанного слева от знака операции, на число двоичных разрядов, указанных справа.
#include
using namespace std;
int main(void)
{unsigned short int j, k, p, q; signed short int n, r, s;
cout.fill(’.’); p=32768; r=32768;
cout<<"unsigned short signed short"<cout<<"
int int"<for (k=1; k<=16; k++)
{ j=1 << k; n=1 << k; q=p>>k; s=r>>k; cout << 1 << "<<" ;
cout.width(2); cout << k << " = ";
cout.width(6); cout << j << "
" << 1 << "<<";
cout.width(2); cout << k << " = ";
cout.width(6); cout << n << "
";
cout << p << ">>" ;
cout.width(2); cout << k << " = ";
cout.width(6); cout << q << "
" << r << ">>";
cout.width(2); cout << k << " = ";
cout.width(6); cout << q <}
return 0;
}
unsigned short signed short int int
1<<.1 = .....2 1<<.1 = .....2 32768>>.1 = .16384
-32768>>.1 = .16384 1<<.2 = .....4 1<<.2 = .....4 32768>>.2 = ..8192
-32768>>.2 = ..8192 1<<.3 = .....8 1<<.3 = .....8 32768>>.3 = ..4096
-32768>>.3 = ..4096 1<<.4 = ....16 1<<.4 = ....16 32768>>.4 = ..2048
-32768>>.4 = ..2048 1<<.5 = ....32 1<<.5 = ....32 32768>>.5 = ..1024
-32768>>.5 = ..1024 1<<.6 = ....64 1<<.6 = ....64 32768>>.6 = ...512
-32768>>.6 = ...512 1<<.7 = ...128 1<<.7 = ...128 32768>>.7 = ...256
-32768>>.7 = ...256 1<<.8 = ...256 1<<.8 = ...256 32768>>.8 = ...128
-32768>>.8 = ...128 1<<.9 = ...512 1<<.9 = ...512 32768>>.9 = ....64
-32768>>.9 = ....64 1<<10 = ..1024 1<<10 = ..1024 32768>>10 = ....32
-32768>>10 = ....32 1<<11 = ..2048 1<<11 = ..2048 32768>>11 = ....16
-32768>>11 = ....16 1<<12 = ..4096 1<<12 = ..4096 32768>>12 = .....8
-32768>>12 = .....8 1<<13 = ..8192 1<<13 = ..8192 32768>>13 = .....4
-32768>>13 = .....4 1<<14 = .16384 1<<14 = .16384 32768>>14 = .....2
-32768>>14 = .....2 1<<15 = .32768 1<<15 = -32768 32768>>15 = .....1
-32768>>15 = .....1 1<<16 = .....0 1<<16 = .....0 32768>>16 = .....0
-32768>>16 = .....0 26

ФОРТРАН:
ISHFT
Возвращает результат cдвига содержимого первого параме-
(i,shift) тра i на shift битов влево при shift ≥ 0 (или вправо при shift < 0). Тип результата совпадает с типом первого пара- метра i. Биты, пересекающие левую или правую границы ячейки, исчезают; а биты, вдвигающиеся в ячейку с противоположной стороны, оказываются нулевыми.
program testconst; implicit none; integer*2 i,ia, ib, ix, iy, k ix=1; iy=32767; write(*,1000)
do k=1,16; ia=ishft(ix,k); ib=ishft(iy,-k)
write(*,1001) k, ia, ia, ia, ia,
ib, ib, ib, ib enddo write(*,’(a,i4 )’) ’ ishft(3, 2)=’, ishft(3, 2)
write(*,’(a,i4 )’) ’ ishft(2,-1)=’, ishft(2,-1)
write(*,’(a,3i4)’) ’ ishft( (/5,5,5/) , (/2,-1,0/) ) =’,&
&
ishft( (/5,5,5/) , (/2,-1,0/) )
1000 format(1x,’Сдвиг : Числа :
Результат сдвига налево :’,&
&
’ Числа :
Результат сдвига направо ’,/&
&
1x,’на
K :
:’,27(’-’),’:’,7x,’:’,27(’-’)/&
&
1x,’бит
: ОДИН
:’,1x,’
двоичной
:
8-й : 16-й :’,&
&
’ 32767 :’,1x,’
двоичной
:
8-й : 16-й ’)
1001 format(1x,i5,i7,b16, o7, z6, i8,b16,o7,z5)
end
Сдвиг : Числа :
Результат сдвига налево : Числа :
Результат сдвига направо на
K :
:---------------------------:
:--------------------------- бит
: ОДИН
:
двоичной
:
8-й : 16-й : 32767 :
двоичной
:
8-й : 16-й
1 2
10 2
2 16383 11111111111111 37777 3FFF
2 4
100 4
4 8191 1111111111111 17777 1FFF
3 8
1000 10 8
4095 111111111111 7777
FFF
4 16 10000 20 10 2047 11111111111 3777 7FF
5 32 100000 40 20 1023 1111111111 1777 3FF
6 64 1000000 100 40 511 111111111 777 1FF
7 128 10000000 200 80 255 11111111 377
FF
8 256 100000000 400 100 127 1111111 177 7F
9 512 1000000000 1000 200 63 111111 77 3F
10 1024 10000000000 2000 400 31 11111 37 1F
11 2048 100000000000 4000 800 15 1111 17
F
12 4096 1000000000000 10000 1000 7
111 7
7 13 8192 10000000000000 20000 2000 3
11 3
3 14 16384 100000000000000 40000 4000 1
1 1
1 15 -327681000000000000000 100000 8000 0
0 0
0 16 0
0 0
0 0
0 0
0
ishft(3, 2)=
12
ishft(2,-1)=
1
ishft( (/5,5,5/) , (/2,-1,0/) ) =
20 2
5 27

1.2.7
Поразрядные (побитовые) логические операции.
СИ:
&
Поразрядное логическое И (and)
∧ Поразрядное исключающее ИЛИ (xor)
|
Поразрядное логическое ИЛИ (or)
∼
Поразрядная инверсия (побитовое отрицание)
Поразрядная инверсия — унарная операция (проводится над всеми битами единственного операнда, указанного справа от нее). Ее назна- чение: инвертирование содержимого операнда (каждый единичный бит заменяется нулевым, а очередной нулевой – единичным). Операция ∼
позволяет изменить знак у содержимого переменной целого типа посред- ством: ∼ k + 1, хотя, вероятно, привычнее -k. Например,
#include
using namespace std;
int main()
// Смена знака числа из m.
Результат:
{int m=5;
//
cout<<"m="<-m="<<-m<<"
m+1="<<m+1<-m=-5
m+1=-5
return 0; }
Остальные операции – бинарные. Результат действия поразрядной опе- рации однозначно определяется соответствующей таблицей истинности:
Операнд Инверсия
1 0
0 1
Операнд 1 Операнд 2 AND OR XOR
1 1
1 1
0 1
0 0
1 1
0 1
0 1
1 0
0 0
0 0
Побитовые операции действуют как обычные конъюнкция, дизъюнк- ция, исключающее ИЛИ, но по отношению к каждому биту. Так
• поразрядная дизъюнкция помещает 1 в те и только те двоичные разряды, в которых эта 1 была хотя бы у одного из операндов.
• поразрядная конъюнкция – в те и только те, в которых 1 была обязательно у обоих операндов.
• Поразрядное исключающее ИЛИ запишет 1 в те и только те разряды, по которым содержимое операндов различалось.
28

Обычные (непоразрядные) логические операции просто вырабатывали одно из значений (1 или 0), которое служило в дальнейшем ключем по- втора или выбора. Поразрядные операции выгодны, когда важен не один ответ типа “ДА/НЕТ”, а формировка значения, представляемого желательным двоичным кодом. Например, пусть необходимо выяснить:
“Есть ли единица в третьем бите (начиная с младшего) двоич- ного представления числа, хранящегося в переменной целого типа?”
Реализуем в одной программе три варианта решения:
#include
#include
using namespace std;
int main()
{int n, f, k, w;
cout<<"введи целое:"; cin>>n; cout<<" n="<w=n;
// сохранение n;
k=0;
// 1-й вариант: a) обнуление номера двоичного разряда.
do
{ f = w % 2; //============: b) нашли текущую младщшую двоичную цифру,
w /=2;
//: c) подготовились к выделению очередной k++;
//: d) нашли номер ее разряда.
}
while ((w!=0) && (k<=2));
//: e) пока он не равен 2 на повтор.
cout<< ( f ? "Есть!"
: "Нет!
")<f= n & 4;
cout<< ( f ? "Есть!!"
: "Нет!! ")<// <--= 2-й вариант f= n & 0x04; cout<< ( f ? "Есть!!!" : "Нет!!!")<k=
17; printf("k=%d %o %0x\n",k, k, k);
w= 021; printf("w=%d %o %0x\n",w, w, w);
n=0x11; printf("n=%d %o %0x\n",n, n, n);
return 0;
}
Иногда удобно в тексте программы целые константы записать в вось- меричной или шестнадцатеричной системах счисления. В СИ константа,
начинающаяся с 0 рассматривается как восьмеричное целое; а код, на- чинающийся двух символов 0x (или 0X) – как шестнадцатеричное. Так константы (17)
10
= (21)
8
= (11)
16
численно равны.
введи целое:6
// Результат работы приведенной выше программы.
n=6
// Вряд ли теперь нужно кого-то убеждать в удобстве
Есть!
// побитовой конъюнкции.
Есть!!
Есть!!!
k=17 21 11
// Демонстрация равеннства (17)_10=(021)_8=(0x11)_16
w=17 21 11
n=17 21 11 29

Аналогичным образом поразрядная конъюнкция позволяет быст- ро находить и остаток от деления целого на любую степень двойки:
#include
using namespace std;
int main()
{ cout<<"38 & 1="<< (38 & 1)<38 - четное число.
// т.к у него в разряде единиц НУЛЬ.
cout<<"38 % 2="<< (38 % 2)<cout<<"(37 &
1)= "<<(37 &
1)<<" = (37 %
2) = "<< (37 %
2)<cout<<"(38 &
3)= "<<(38 &
3)<<" = (38 %
4) = "<< (38 %
4)<cout<<"(38 &
7)= "<<(38 &
7)<<" = (38 %
8) = "<< (38 %
8)<cout<<"(38 & 15)= "<<(38 & 15)<<" = (38 % 16) = "<< (38 % 16)<return 0; }
38 & 1=0
// Результат работы.
Если число делится нацело на 2**n, то
38 % 2=0
// все младшие цифры его двоичного пред-
(37 &
1)= 1 = (37 %
2) = 1
// ставления от 0-й до (n-1)-ой нулевые.
(38 &
3)= 2 = (38 %
4) = 2
// Если же не делится, то именно они и
(38 &
7)= 6 = (38 %
8) = 6
// есть величина остатка.
(38 & 15)= 6 = (38 % 16) = 6
Поразрядное исключающее ИЛИ получает код отличия содер- жимого одной переменной от содержимого другой переменной. Поэтому,
изменив содержимое одной из них на этот код, всегда можно повтор- ным применением этой же операции к тем же переменным восстановить замененное, то есть (a
∧
b)
∧
a ≡ a.
Подобный прием очень полезен на практике. Например, пусть надо об- менять содержимым две переменные a и b целого типа, не используя дополнительной рабочей переменной. Реализуем решение двояко:
на базе на базе арифметических a=17
поразрядного a=010001
операций b=43 исключающего ИЛИ b=101011
+ и -
∧
a=a+b a=60
a = a
∧
b a=111010
b=a-b b=17
b = a
∧
b b=010001
a=a-b a=43
a = a
∧
b a=101011
в одной и той же программе (для сравнения результатов).
30

#include
using namespace std;
int main()
{ short int a, b, c, d;
cout<<"Введите два целых значения"<cin>>a>>b;
c=a; d=b; cout<<" a="<< a<<" b="<< b <<"
c="<< c<<" d="<< d <a+=b;
c^=d; cout<<"
a+=b = "<c^=d = "<b=a-b; d=c^d; cout<<" b=a-b = "<d=c^d = "<a-=b;
c^=d; cout<<"
a-=b = "<c^=d = "<cout<<" a="<< a<<" b="<< b <<"
c="<< c<<" d="<< d <return 0;
}
Введите два целых значения a=43 b=17
c=43 d=17
// Интересно посмотреть на работу a+=b = 60
c^=d = 58
// этой программы, когда сумма чисел b=a-b = 43
d=c^d = 43
// выходит за границы допустимого a-=b = 17
c^=d = 17
// для выбранного типа данных диапазона a=17 b=43
c=17 d=43
// например, а=25000 и b=15000.
Введите два целых значения a=25000 b=15000
c=25000 d=15000
a+=b = -25536
c^=d = 23344
b=a-b = 25000
d=c^d = 25000
a-=b = 15000
c^=d = 15000
a=15000 b=25000
c=15000 d=25000
ФОРТРАН
вместо упомянутых операций СИ содержит соответствую- щие встроенные функции с параметрами целого типа.
iand(i, j) – поразрядная конъюнкция.
ieor(i, j)
– действие поразрядного исключающего ИЛИ.
ior(i, j)
– поразрядная дизъюнкция (неисключающее ИЛИ)
not(i)
– поразрядная инверсия (побитовое отрицание)
Современный ФОРТРАН позволяет записывать целые числа и в восьме- ричной, и в шестнадцатеричной, и в двоичной системах счисления:
program tstbit1; implicit none ! Задание констант в 2-, 8-, 16-й системах integer a, b,c, d,e, f,g
!
счисления:
a=10; b=B’1010’; c=b’1010’
! Результат работы программы :
d=O’12’
; e=o’12’
! a= 10 b= 10 c= 10 d= 10 e= 10 f= 10 g= 10
f=Z’A’
; g=z’A’
!===========================================
write(*,’(7(a,i3))’) ’ a=’, a,’ b=’,b,’ c=’, c,’ d=’,d,&
&
’ e=’, e,’ f=’,f,’ g=’, g end
31

program testbit2; implicit none ! ФОРТРАН-программа, выясняющая есть ли integer n, f, k, w
!
у введенного целого единица в разряде character*8 a(0:1) /’
Нет!
’,’
Есть! ’/ !
его двоичных сотен.
write(*,*) ’введи целое:’; read(*,*) n; write(*,*) ’ n=’,n w=n;
! 1-ый вариант:
сохранили n k=0;
!
a) обнуление номера двоичного разряда.
do; f = mod(w, 2)
!
b) нашли текущую младщшую двоичную цифру,
w = w / 2
!
c) подготовились к выделению очередной k=k+1
!
d) нашли номер ее разряда.
if (w.eq.0 .or. k>2) exit
!
e) как только найден бит двоичных enddo
!
сотен --> выйти из данного цикла.
write(*,*)
a(f)
f=iand(n, 4);
write(*,*) a(f/4)
! 2-й вариант f=iand(n, z’4’); write(*,*) a(f/4)
! 3-й вариант.
write(*,1001) ’ n=’,n
!
Двоичный код однобайтового числа write(*,1001) ’ 4=’,4
!
можно вывести по формату b8,
1001 format(1x,a,3x,b8)
!
а четырёхбайтового по формату b32.
end
Варианты пропуска программы для n=16 и n=36
------------------------------------------- введи целое:
введи целое:
16 36
n=
16
n=
36
Нет!
Есть!
Нет!
Есть!
Нет!
Есть!
n=
10000
<-- двоичные
-->
n=
100100 4=
100
<-- коды на печати -->
4=
100
program testbit5
! Реализация на ФОРТРАНе обмена содержимым двух implicit none
! целых переменных без третьей переменной двумя integer a, b, c, d;
! способами: арифметическим и посредством write(*,*) ’Введите два целых значения’;
! исключающего ИЛИ.
read (*,*) a, b
!......................
c=a; d=b;
write(*,*) ’ a=’, a, ’ b=’,b,’
c=’,c,’ d=’,d a=a+b;
c=ieor(c,d); write(*,*)’ a=a+b = ’,a,’
c=ieor(c,d)=’,c b=a-b;
d=ieor(c,d); write(*,*)’ b=a-b = ’,b,’
d=ieor(c,d)=’,d a=a-b;
c=ieor(c,d); write(*,*)’ a=a-b = ’,a,’
c=ieor(c,d)=’,c write(*,*) ’ a=’, a, ’ b=’,b,’
c=’,c,’ d=’,d end
Введите два целых значения
<--= Результат пропуска
17 43
программы testbit5
a= 17 b= 43
c= 17 d= 43
a=a+b =
60
c=ieor(c,d)= 58
b=a-b =
17
d=ieor(c,d)= 17
a=a-b =
43
c=ieor(c,d)= 43
a= 43 b= 17
c= 43 d= 17 32

1.2.8
Ещё один пример на побитовые
Решаем задачу подсчёта числа единиц в записи целого значения после его перевода в двоичную систему счисления). Обычное школьное решение:
после ввода целого значения N алгоритм сводят к циклу с предуслови- ем, не используя побитовые операции (здесь приведены соответствующие
ФОРТРАН- и СИ-программы):
program testbit0; implicit none; integer, parameter :: kmax=100000000
integer N, m, k, s; real t0, t1
read(*,*) N; write(*,*) ’N=’,N; call cpu_time(t0)
do k=1,kmax s=0; m=N; do while (m>0); s=s+mod(m,2);
m=m/2; enddo enddo call cpu_time(t1);
write(*,*) ’ s=’,s,’ time=’,t1-t0
end program testbit0
#include
#include
int main(void)
{ const int kmax=100000000; int N, m, k, s; clock_t t0, t1;
scanf("%d",&N); printf(" N=%d\n",N);
t0=clock();
for (k=1; k<=kmax; k++) { s=0; m=N; while (m>0) {s=s+m%2; m=m/2;} }
t1=clock();
printf(" s=%d time=%7.2f",s, (double)(t1-t0)/CLOCKS_PER_SEC); return 0;
}
Время работы алгоритмов testbit0 зависит от числа цифр в числе. В таб- лице ниже, в колонках Ф (ФОРТРАН) и С (СИ), приведены в секундах временные затраты 10 8
-кратного расчёта количества единиц для двух значений N=16 и N=2147483647:
Оптимизация:
-O0
-O1
Алгоритм
N
s
Ф
СИ
Ф
СИ
testbit0 2
4 1
2.6 2.0 1.5 1.2 2
31
− 1 31 14.5 14.4 8.1 8.7
Вообще говоря, ничего удивительного. Для N=16 тело цикла будет по- вторяться 5 раз, а для N=2147483647 — 31 раз. Поэтому временн ´
ые затраты для последнего N должны быть примерно в шесть раз больше чем для первого, что и наблюдается. Теперь продемонстрируем насколь- ко быстрее работает приведённый в [16, 15] алгоритм, который исполь- зует побитовые операции.
33

Время его работы не зависит от количества цифр во вводимом числе,
так, что результат для любого 32-битного целого получается за время чуть ли не вдвое меньшее времени, затраченного testbit0 при N=16.
program testbit1; implicit none; integer, parameter :: kmax=100000000
integer N, m, k, s; real t0, t1
read(*,*) N; write(*,*) ’N=’,N
call cpu_time(t0)
do k=1,kmax s=N;
s=iand(s,z’55555555’)+iand(ishft(s, -1),z’55555555’)
s=iand(s,z’33333333’)+iand(ishft(s, -2),z’33333333’)
s=iand(s,z’0f0f0f0f’)+iand(ishft(s, -4),z’0f0f0f0f’)
s=iand(s,z’00ff00ff’)+iand(ishft(s, -8),z’00ff00ff’)
s=iand(s,z’0000ffff’)+iand(ishft(s,-16),z’0000ffff’);
enddo call cpu_time(t1); write(*,*) ’ s=’,s,’ time=’,t1-t0
end program testbit1
#include
#include
int main(void)
{ unsigned int w, N;
const int kmax=100000000; int k, s; clock_t t0, t1;
scanf("%i",&N);
printf(" w=%i
%x\n",N,N);
t0=clock();
for (k=1;k<=kmax;k++)
{
s=N; s=(s&0x55555555)+((s>> 1)& 0x55555555);
s=(s&0x33333333)+((s>> 2)& 0x33333333);
s=(s&0x0f0f0f0f)+((s>> 4)& 0x0f0f0f0f);
s=(s&0x00ff00ff)+((s>> 8)& 0x00ff00ff);
s=(s&0x0000ffff)+((s>>16)& 0x0000ffff);
}
t1=clock();
printf(" s=%d time=%7.2f",s, (double)(t1-t0)/CLOCKS_PER_SEC); return 0;
}
Соответствующие результаты для тех же параметров расчёта:
Оптимизация:
-O0
-O1
Алгоритм
N
s
Ф
СИ
Ф
СИ
testbit1 2
4 1
1.1 1.3 0.06 0.05 2
31
− 1 31 1.1 1.3 0.06 0.05 34

Идея алгоритма testbit1.
На входе четырёхбайтовое целое N (или s),
записанное 32-мя двоичными цифрами: какие-то из них 0, какие-то 1.
Количество последних нужно узнать.
1. Пусть исходное
N = 10111100011000110111111011111111
(2)
(см. [16]).
2. Любую цифру двоичной записи можно рассматривать и как число,
обозначающее сколько единиц находится в данном двоичном разря- де: 0 — нуль единиц; 1 — одна единица.
3. Побитовая операция умножения и сдвига позволяют получить в ка- честве слагаемых наборы битов из чётных и нечётных позиций ис- ходного N. Их одно сложение даст сумму каждой из 16 пар соседних битов, т.е. количество единиц в соответствующей паре:
1 2
2 0
1 1
0 2
1 2
1 2
2 2
2 2
Двоичный код этих 16 сумм
01 10 10 00 01 01 00 10 01 10 01 10 10 10 10 10 Именно его даёт алгоритм.
4. Аналогично за одно сложение организуется одновременный расчёт
8 сумм (по сумме на каждую пару соседних чисел, полученных в предыдущем пункте), находя, тем самым, количество единиц в со- ответствующих тетрадах исходного двоичного представления N.
3 2
2 2
3 3
4 4
Двоичные коды этих 8 чисел.
0011 0010 0010 0010 0011 0011 0100 0100
Именно его получает алгоритм
5. Следующее очередное сложение находит суммы четырёх пар сосед- них чисел, полученных в предыдущем пункте. В итоге находятся количества единиц в каждом байте исходного представления N:
5 4
6 8
Двоичные коды этих четырёх чисел.
0101 0100 0110 1000
Именно их получает алгоритм.
6. По той же схеме за одно сложение находятся суммы 9 и 14 9
14
Двоичные коды этих двух чисел.
1001 1110
Именно их получает алгоритм.
35

7. Наконец, последнее (пятое) сложение даёт
23
Одно число равное числу единиц в исходном N
Двоичный код этого числа.
10111
Именно его получает алгоритм
(16+7=23).

16>16>15>15>14>14>13>13>12>12>11>11>10>10>

1   2   3   4   5   6   7   8   9   ...   23