Начинающим программистам. Этап 2.

← →
Юрий Зотов (2002-10-28 23:15) [0]

Итак, идем дальше. Сначала контрольные упражнения по заданию 1 (упражнения 1, 2 и 3 - это классика, их надо запомнить навсегда).

1. Доказать, что в любой позиционной системе счисления ее основание имеет вид 10.

2. Принимая, что отрицательные числа хранятся в дополнительном коде, доказать, что число -1 в N-разрядном машинном коде записывается в виде N единиц при любом N.

3. Доказать, что машинная операция (I shl N) эквивалентна умножению I на 2^N, а машинная операция (I shr N) эквивалентна целочисленному делению I на 2^N (запись "2^N" означает "2 в степени N").

4. Учитывая, что в Паскале False - это ноль, а True - это единица, доказать, что:
а). логические выражения (I < 0) и (I shr 31) эквивалентны, если I есть 32-битное целое.
б). логическое выражение (I and 1) эквивалентно вызову функции Odd(I) (см. в хелпе).

5. В двухбайтовом шестнадцатиричном выражении FE40 and not (A2B1 or 5D) xor AEC
а). проверить, установлен ли 7-й или 11-й бит.
б). проверить, установлены ли 7-й и 11-й биты.
в). установить 4-й и 12-й биты, сбросить 3-й, 8-й и 13-й биты.
г). разложить результат на старший и младший байты.
При вычислении выражения принять старшинство операций, как в Delphi (см. в хелпе: "Operator precedence"). Не забыть, что нумерация битов идет справа налево и начинается с нуля.

Ответы к упражнению 5 привожу сразу, но для Вас же лучше сначала получить их самостоятельно. Сначала вычисляем результат выражения, учитывая скобки и приоритет операций:
A2B1 or 5D = A2FD
not A2FD = 5D02
FE40 and 5D02 = 5С00
5С00 xor AEC = 56EC
Это и есть конечный результат. Теперь даем ответы:
а). 56EC and 880 не равно нулю - значит, либо 7-й, либо 11-й бит, либо оба вместе установлены.
б). 56EC and 880 не равно 880 - значит, 7-й и 11-й биты одновременно НЕ установлены.
в). 56EC or 1010 and not 2108 (получим 56F4)
г). 56EC shr 8 - дает старший байт (равен 56)
56EC and FF - дает младший байт (равен EC)

Теперь, прорешав все упражнения и твердо (надеюсь) усвоив пройденный материал, делаем из него выводы и пытаемся распространить их на Delphi.

1. Любое число имеет величину и строковое представление. Величина всегда невидима и не зависит ни от чего. Видим же мы ТОЛЬКО строковое представление, и ТОЛЬКО оно зависит от системы счисления. В машине все числа хранятся в 2-ной системе, а в Delphi-программе мы можем использовать либо 10-ную, либо 16-ную запись (причем признаком 16-ной записи является симол "$" в начале числа). Обе формы совершенно равносильны и полностью взаимозаменяемы - то есть, везде, где можно написать, например, 255, с тем же успехом можно написать $FF (и наоборот). 16-ная запись является сокращенной формой 2-ной записи, но прямую 2-ную запись Delphi не поддерживает (хотя ее можно использовать в ассемблерных вставках).

2. Часто задаваемые вопросы типа "как перевести значение числа из одной системы в другую" просто бессмысленны. Перевести ЗНАЧЕНИЕ (то есть, величину) числа нельзя никак, потому что оно всегда одно и то же. Перевести можно ТОЛЬКО строковое представление числа, и в Delphi есть две функции, возвращающие строковые представления чисел - IntToStr (10-ное) и IntToHex (16-ное). Есть также обратная им функция StrToInt, дающая значение числа по его 10-ному или 16-ному строковому представлению. Есть и другие (Format, StrToIntDef и пр. - см. справку).

Пример перевода 10-ной записи в 16-ную: IntToHex(StrToInt(Edit1.Text)).
Пример обратного перевода: IntToStr(StrToInt("$" + Edit1.Text)).
В обоих случаях, если текст в Edit1 не является правильным представлением числа, возникнет ошибка.

Теперь разберем, как процессор (CPU) выполняет арифметические действия с целыми числами. Сразу оговорюсь, что приводимый ниже материал не является абсолютно точным. Он является верным лишь ПО СМЫСЛУ, поскольку нам сейчас гораздо важнее понятность материала, а не его точность. Любителей абсолютной точности отсылаю к книгам по CPU и Ассемблеру.

Когда мы делаем арифметические операции вручную, то часто говорим - "на ум пошло". У CPU ума нет, но зато у него есть регистр флагов. Это просто набор битов, в котором значение каждого бита имет вполне определенный смысл. Младший бит в этом регистре называется "флаг переноса" (CF - carry flag). Вот он-то и есть тот самый "ум", на который "пошло". Этот бит аппаратно устанавливается в 1, если происходит перенос в старший разряд, либо заем из старшего разряда (или в ноль, если переноса/заема не происходит). Поскольку CPU использует двоичную систему, то нет необходимости помнить, сколько именно переносится или занимается (всегда единица), достаточно помнить сам факт переноса или заема - а для этого нужен всего 1 бит, которым и служит флаг CF. Ясно, что перенос в несуществующий разряд (или заем из него) означает выход за разрядную сетку.

11-й бит в том же регистре называется "флаг переполнения" (OF - overflow flag). Он аппаратно устанавливается в 1, когда при знаковых операциях происходит перенос в старший (знаковый) разряд - что тоже означает выход за разрядную сетку.

=== см. окончание ===

← →
Юрий Зотов (2002-10-28 23:19) [1]

=== окончание ===

Возникает вопрос - а что такое "знаковая операция"? Вспомним, что старший бит целого числа дает его знак (1-минус, 0-плюс). Но ведь можно считать и так, что само число всегда положительно, а старший бит является его частью, а никаким не знаком. То есть, целое число может интерпретироваться двояко - как знаковое и беззнаковое. Беззнаковые числа не могут быть отрицательными, но зато их максимальное значение вдвое больше, чем у знаковых (из-за лишнего бита в разрядной сетке) - например, Cardinal и Integer в Delphi. Так вот, знаковая операция - это операция над знаковыми числами.

Самое удивительное, что при сложении (а вычитание - это то же самое сложение, только у второго операнда сначала меняется знак) CPU не различает знаковые и беззнаковые числа, но, тем не менее всегда получает верный результат. В этом ему помогают дополнительная кодировка чисел (вспомнили?) и флаги CF и OF.

Рассмотрим 4 случая сложения однобайтовых чисел в различных представлениях.

Двоичное Беззнаковое Знаковое CF OF

11111001 249 -7
00000010 2 +2
11111011 251 -5 0 0
верно верно

11111100 252 -4
00000101 5 +5
00000001 1 +1 1 0
ошибка верно

01111001 121 +121
00001011 11 +11
10000100 132 -124 0 1
верно ошибка

11110110 246 -10
10001001 137 -119
01111111 127 +127 1 1
ошибка ошибка

Таким образом, по завершении операции сложения/вычитания ее правильность определяется типом операндов (знаковые-беззнаковые) и состоянием флагов CF и OF. Ошибка может приводить к генерации исключения, либо игнорироваться (детали реализации опускаю, скажу лишь что в Delphi за это отвечают директивы компилятора $Q и $R, а также птички "Overflow checking" и "Range checking" на вкладке "Compiler" в опциях проекта).

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

А теперь - следующее задание (№ 2). Срок выполнения - 3 недели, потом пойдем дальше. Имейте в виду - задание большое и ответственное(поэтому и срок довольно большой), так что расслабляться некогда.

1. По книгам или по хелпу (см. "Integer types") разобраться со ВСЕМИ целыми типами Delphi (а их всего 9). Твердо помнить, какие из них знаковые, а какие - беззнаковые, каков их размер в памяти и диапазон возможных значений. Разобраться с функциями SizeOf, Low, High, Succ, Pred, Inc и Dec. Уяснить, что при вычислении смешанных арифметических выражений (с операндами разных типов) младшие типы могут приводиться к старшим. Знать все целочисленные операции, включая Div и Mod (см. в хелпе "Arithmetic operators") и понимать разницу между унарными (одноместными) и бинарными (двуместными) операциями "+" и "-". Раз и навсегда запомнить, что операции "плюс" и OR - это не одно и то же (5 + 1 = 6, а 5 or 1 = 5, хотя 4 + 2 = 6 и 4 or 2 = 6). Выучить старшинство (приоритет) операций над целыми числами (см. "Operator precedence" в хелпе).

2. Открыть текст модуля Windows.pas и посмотреть соответствие встроенных типов Delphi типам UCHAR, SHORT, DWORD, UINT, ULONG, LONGLONG, а также THandle, HWND, HHOOK, HMODULE, HINST и другие "H". Понять систему наименований ("U" означает "unsigned" - беззнаковый, а "H" означает "Handle"). Усвоить, что все "хэндлы" - это просто-напросто беззнаковые 4-х байтовые целые.

ВНИМАНИЕ: типы, начинающиеся с буквы "P" или значка "^" пока даже и не пытайтесь рассматривать!!! Ни в коем случае!!!

3. Открыть модуль Messages.pas и посмотреть, что из себя представляют константы WM_xxx. Это и есть знаменитые сообщения Windows - а они всего лишь числа, оказывается.

4. По ссылкам из задания № 1 разобраться с двоичной кодировкой чисел с плавающей точкой (вещественных). Понять, что в памяти они хранятся в виде "научной" нотации (мантисса-экспонента), что в большинстве случаев эти числа округляются и почему это так. По книгам или хелпу (см. "Real types") разобраться с вещественными типами Delphi, знать размер в памяти, дипазон и точность каждого типа, а также особенности Comp и Currency. Посмотреть типы TDate, TTime и TDateTime и запомнить, что это по сути тот же самый Double. Посмотреть все функции из раздела "Arithmetic routines" в хелпе. Знать директиву компилятора $REALCOMPATIBILITY.

5. Зайти на "Королевство Delphi" ( http://www.delphikingdom.com) в раздел "Hello, world!", а там найти статью Антона Григорьева "Неочевидные особенности вещественных чисел" и самым внимательным образом ее ИЗУЧИТЬ и ПОНЯТЬ (это ОЧЕНЬ важно, иначе можете потом натолкнуться на кучу подводных камней). Знать, что такое машинный ноль и машинное эпсилон, когда и как возникает исчезновение порядка, что такое Underflow. Понимать, что для вешественных чисел проверка if X=Y может не сработать и почему.

Успехов!

← →
Юрий Зотов (2002-10-28 23:21) [2]

P.S.
Этап 1 см. здесь:
http://delphi.mastak.ru/cgi-bin/forum.pl?look=1&id=1035226023&n=3

← →
Юрий Зотов (2002-10-29 11:38) [3]

1. Up.
2. Напоминаю просьбу ко всем - не замусоривать эту ветку вещами, напрямую к ней не относящимися. Для мнений, пожеланий и пр. используйте другие ветки, please.

← →
Юрий Зотов (2002-10-29 23:47) [4]

Народ, не слышно реакции. Это еще кому-нибудь нужно? Приступили к выполнению 2-го задания, или как?

← →
Malder (2002-10-30 00:06) [5]

статья Антона Григорьева "Неочевидные особенности вещественных чисел http://www.delphikingdom.com/helloworld/reals.htm

← →
Neox (2002-10-30 00:16) [6]

Приступаем к выполнению :)
Спасибо Юрию Зотову за терпение и желание учить!

← →
al_ (2002-10-30 00:51) [7]

Заканчиваю первое и с четверга смогу приступить ко второму этапу. Приятно что мы еще кому-то нужны =) Если можно, чуточку больше времени выделять для работы над этапом. А то работа еще, блин.

← →
RV (2002-10-30 08:50) [8]

al_ © (30.10.02 00:51)
А то работа еще, блин.

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

← →
lipskiy (2002-10-30 23:45) [9]

Весь последний материал выложен на http://delphi.adlen.ru

← →
Dmk (2002-10-30 23:52) [10]

Занятно :) Спасибо. Решил присоедениться.
Повторить никогда не помешает.

← →
DeMoN-777 (2002-10-31 12:28) [11]

Юрий огромное Вам спасибо, всё своё свободное время уделяю процессу обучения. Трудновато начинать с нуля =(, ведь я и понятия не имел о такий числах =).
Учится, учится и ешё раз учится. Стараюсь не задавать вопросов и сам пытаюсь во всё въехать.

>lipskiy © (30.10.02 23:45)
Для интереса поставь на титулку сайта счётчик.

>ALL
Извените что "слегка засорил" такую информационную ветку.

← →
F1 (2002-10-31 12:48) [12]

Присоединяюсь к обучению! Спасибо Юрию Зотову за это все.
А то сам бы не догадался с этим покопаться :-)

← →
Юрий Зотов (2002-10-31 13:14) [13]

> DeMoN-777 and All

> Стараюсь не задавать вопросов и сам пытаюсь во всё въехать.

Это правильно (иначе какая же учеба?), НО: если что-то все же не получается или остается непонятным - ОБЯЗАТЕЛЬНО задавайте вопросы.

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

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

← →
Юрий Зотов (2002-10-31 13:17) [14]

> lipskiy © (30.10.02 23:45)

Tnx. Приступил к продолжению письма (скорее всего, отошлю в выходные). Прошу по возможности ускорить интерактив.

← →
Malder (2002-11-02 10:14) [15]

UP что ли

← →
DeMoN-777 (2002-11-06 23:59) [16]

Не дам умереть ветке.

← →
Pascal's programmer (2002-11-07 01:48) [17]

> Malder © (02.11.02 10:14)
> UP что ли
>
>
> DeMoN-777 © (06.11.02 23:59)
> Не дам умереть ветке.

а зачем такие сложности? Разве трудно эту ветку в букмарки (CTRL+D) добавить?

← →
Ru (2002-11-07 18:34) [18]

Если подойдет словесное доказательство:
1

10-тичная |2-ичная |16-тиричная|
====================================|
число|номер |число|номер|число|номер|
====================================|
0 |1 |0 |1 |0 |1
1 |2 |1 |10 |1 |2
2 |3 | |2 |3
3 |4 | |3 |4
4 |5 | |4 |5
5 |6 | |5 |6
6 |7 | |6 |7
7 |8 | |7 |8
8 |9 | |8 |9
9 |10 | |9 |a
|a |b
|b |c
|c |d
|d |e
|e |f
|f |10

← →
StAL (2002-11-07 21:48) [19]

Хотелось-бы присоединится.
Начал читать статьи, но перед этим прочитал все ветки, относящиеся к обучению.
Мне только 15 лет, и я не знаю, стоит ли мне браться за это?
Вроде-бы среди сверстников я единственный отличник по информатике, меня приглашают на олимпиады, но среди Вас, я - никто.
Пожалуйста, посоветуйте что-нибудь.
Кстати насчет LParam, у меня действительно получилось разобраться!
А раньше я просто тупо скатывал это из FAQ
Спасибо всем, и, особенно, Юрию Зотову.
С ув. Алексей

← →
Pascal's programmer (2002-11-07 23:31) [20]

> StAL © (07.11.02 21:48)

> но среди Вас, я - никто.

Да ну? А мне значит 15 лет и я тоже никто? Парень, причем тут возраст? Я в форуме 18-22 летним "куль программерам" на дурацкие вопросы тут задолбался отвечать уже!
+ты же участвуешь во всяких там олимпиадах (и что-то умудряешься занять), а это уже оооочень хорошо!!!

← →
StAL (2002-11-08 10:02) [21]

> Pascal"s programmer © (07.11.02 23:31)

Ну спасибо. Тогда, значит, я присоединяюсь.
Юрий Зотов, спасибо за прекрасную идею!
С ув. Алексей

← →
Николай Быков (2002-11-08 10:11) [22]

> StAL © (08.11.02 10:02)

Знал бы ты чья это идея была ;-)
Юрий Зотов только согласился удовлетворить просьбу, за что ему спасибо

← →
Юрий Зотов (2002-11-08 12:37) [23]

> Мне только 15 лет, и я не знаю, стоит ли мне браться за это?

Если есть интерес и желание, то стоит. 15 лет - это старшие классы школы. Возраст и знания вполне достаточные. Хотя грамотный программист, по идее, должен бы знать и численные методы, которые изучают в ВУЗах. Но это уж потом, как говорится.

← →
PaRL (2002-11-10 18:26) [24]

У меня вопрос про числа с плавающей точкой.

"хранимый порядок = истинный порядок + смещение"

Я не понимаю зачем смещение, если можно хранить просто порядок в двоичном виде.

← →
Marser (2002-11-10 21:36) [25]

> Юрий Зотов

А не проще выложить в раздел "статьи"?

← →
StAL (2002-11-11 15:26) [26]

У меня возник вопрос насчет пятого задания.
До 56ЕС дохожу, а дальше...
а). 56EC and 880 не равно нулю - значит, либо 7-й, либо 11-й бит, либо оба вместе установлены. - Откуда 880???
б). 56EC and 880 не равно 880 - значит, 7-й и 11-й биты одновременно НЕ установлены. - Почему???
в). 56EC or 1010 and not 2108 (получим 56F4) Откуда 1010 и 2108???
г). 56EC shr 8 - дает старший байт (равен 56)-Это вроде понятно
56EC and FF - дает младший байт (равен EC)
Это уже после 100 попытки разобраться.
Ничего не понимаю.
Подскажите пожалуйста.
С ув. Алексей
ЗЫ
2 Юрий Зотов
> Если есть интерес и желание, то стоит.
БОЛЬШОЙ Интерес и желание ЕСТЬ!!!!
Спасибо Вам большое!

← →
StAL (2002-11-11 15:35) [27]

И с заданием 2 что-то никак.
Может я тупой, но прочитав статьи, я все понял кроме этого(2 и 5)
Спасибо Вам.

← →
Юрий Зотов (2002-11-12 10:26) [28]

> StAL

Задание 2.

Пусть у нас есть 2-ное число, состоящее из N единиц:
111...1

Прибавив к нему единицу, получим число, состоящее из единицы и N нулей:
1000...0

Если сетка ограничена N разрядами, то старший бит в нее не помещается и остается просто N нулей - что означает ноль.

Итак, мы к какому-то число прибавили единицу и получили ноль. Значит, первоначальное число было равно -1. Вывод: в N-разрядном дополнительном коде число -1 записывается в виде N единиц при любом N.

Задание 5.

Если через Х обозначить произвольное состояние бита (0 или 1), то легко убедиться, что:
X or 1 - всегда 1
X and 0 - всегда 0
X and 1 - всегда X

Эта табличка используется для проверки и установки состояний бит. Пусть у нас есть двоичное число XXXXXXXX и нужно проверить, установлен ли в нем бит 2 или 7 (то есть, равен ли хотя бы один из них 1). Произведя операцию AND с числом 10000100 (маской), получим X0000X00. Если результат равен нулю, то оба бита нулевые, если нет - то хотя бы один из них единичный. Далее, если этот же результат равен самой маске, то оба бита единичные, а если нет - то хотя бы один из них нулевой.

В задании нужно было проверить 7-й и 11-й биты. Значит, наша маска должна быть записана как 0000100010000000 (или 880 в 16-ном виде).

Для установки 4-го и 12-й бита нужно произвести операцию OR с маской 0001000000010000, а для сброса 3-го, 8-го и 13-й бита - операцию AND с маской (NOT 0010000100001000). Эти числа и есть 1010 и 2108 в 16-ном виде.

Вот такая подсказка. Попробуйте разобраться в задании еще раз, если не получится - спрашивайте.

← →
al_ (2002-11-12 20:44) [29]

Вот мои действия:
1ABC,9D(hex) -> 0001(1) 1010(A) 1011(B) 1100(C),1001(9) 1101(D) (bin)
целую часть разбиваю на триады для перевода в восьмеричную с права налево. А как разбивать дробную часть на триады справа налево или наоборот?
и что-то не получается у меня вот эти 2 операции $B,92 - $D,11 и 1110,11(b) - 10001(b) откуда заем брать? :(
5. Дайте ссылочку по унарным и бинарным опциям, а то везде на С++ натыкаюсь ! :(

← →
StAL (2002-11-14 18:04) [30]

Спасибо!!!
С 5-тым разобрался полностью. Решил еще 10 заданий такого типа.
Даже как-то радостно стало!

> al_
И у меня такой вопрос.
Как переводить из 16тиричной в 2ичную дроби?
Спасибо еще раз!
С ув.Алексей
PS
Кстати, кто успел скачать Лекцию99. Там сейчас 404 Не найдено.
Может вышлете? mailto:stalcom@ua.fm
Спасибо заранее

← →
al_ (2002-11-15 03:00) [31]

← →
Юрий Зотов (2002-11-15 08:20) [32]

Информация для всех.

Для ЦЕЛЫХ чисел ОЧЕНЬ важно понимать их 2-ную (16-ную) кодировку, уметь делать перевод из системы в систему, знать прямой, обратный и дополнительный коды, уметь выставлять и проверять отдельные биты, понимать знаковую/беззнаковую интерпретацию и т.д.

Для ВЕЩЕСТВЕННЫХ же чисел достаточно иметь лишь общее представление об этих вещах. Зато для них нужно четко знать научную нотацию и понимать особенности машинной арифметики. Поэтому не стоит сильно увлекаться переводом вещественных чисел из системы в систему, гораздо важнее четко усвоить то, о чем пишет в своей статье Антон Григорьев (ссылку см. в задании).

Примерно через неделю предполагаю выдать контрольные вопросы по вещественным числам и новое задание. Успеваете?

← →
RV (2002-11-15 08:40) [33]

> Успеваете?

я - да.

СПАСИБО

← →
onix (2002-11-15 10:36) [34]

Успеваю.

Спасибо.

← →
al_ (2002-11-15 22:41) [35]

> Успеваете?

Не совсем. Еще бы немножко времени! Если бы еще и ссылочек побольше!

← →
cypher (2002-11-15 23:11) [36]

Предлагаю еще одну классику, малюсенькую прогу...
тем кто знает молчать,а то не интересно.

итак, вывести введенную пользователем последовательность чисел наоборот, т.е. запускаем прогу.. вводим a1,a2,a3...aN потом говорим, что все, надоело, и программа выводит aN,a(N-1)...a2,a1. Причем НЕ ИСПОЛЬЗОВАТЬ МАССИВ.

← →
cypher (2002-11-15 23:13) [37]

на обдумывание 3 минуты, не успели, Вам минус! =)

← →
Aristarh (2002-11-15 23:20) [38]

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

А на счет 3-х минут зря. Не обязательно человек прочтет сразу или коннект плохой

← →
cypher (2002-11-15 23:21) [39]

прочитал, осознал... есть три минуты.
вариант строки - плохой, это уже не числа, а потом строка - тот же массив =)

← →
Aristarh (2002-11-15 23:24) [40]

Начинающим программистам. Этап 2. Найти похожие ветки