ДС20в02-представление-целых (1238923), страница 2

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

Текст из файла (страница 2)

коде визуальноПереполнениеотрицательными¢ЗначенияTAdd4(u , v)§ 4-ре бита в доп. коде§ Диапазон от -8 до +7¢Отсечение§ Если сумма ≥2w–1Результатотрицательный§ Не более 1 раза§ Если сумма < –2w–1§ Результатположительный§ Не более 1 раза§864206-242-40-6-2-8-8-4-6-4u-2-6024v-86Переполнениеположительными40Умножение¢Вычисление полного произведения w-битовых чисел x, y§ Или знаковых или беззнаковых¢Границы§ Беззнаковые: 0 ≤ x * y ≤ (2w – 1) 2 = 22w – 2w+1 + 1До 2w бит§ Минимальное в доп.коде: x * y ≥ (–2w–1)*(2w–1–1) = –22w–2 + 2w–1§ До 2w–1 бит§ Максимальное в доп коде : x * y ≤ (–2w–1) 2 = 22w–2§ До 2w бит, но только для (TMinw)2§¢Обеспечение полноты результата§ Необходимо расширение слова для каждого результата§ Реализуется лишь в программных пакетах арифметики“произвольной точности”41Умножение беззнаковыхu* vОперанды: w битПолное произведение:u2*w битБез w старших бит:w младших бит¢·v•••UMultw(u , v)••••••••••••Стандартное умножение беззнаковых в Cи§ Игнорирует старшие w бит§ Реализует умножение по модулюUMultw(u , v)=(u · v) mod 2w42Умножение знаковыхu* vОперанды: w битПолное произведение:u2*w бит·vБез w старших бит:w младших бит¢•••TMultw(u , v)••••••••••••Стандартное умножение знаковых в Cи§ Игнорирует старшие w бит§ Некоторые из них различаются для знакового ибеззнакового умножений§ Младшие биты такие-же43Умножение сдвигом на степень двойки¢Операция§ u << k даёт u*2k§ Для знаковых и беззнаковыхОперанд: w битПолное произведение:w+k битБез k старших бит:w младших бит¢Примерыku* 2k•••0u · 2k•••UMultw(u , 2k) •••TMultw(u , 2k)•••0 1 0•••0 00•••0 00•••0 0§ u << 3==u * 8§ u << 5 - u << 3==u * 24§ Большинство машин сдвигает и складывает быстрее умножения§Компилятор создаёт соответствующий код автоматически44Биты, байты и целые¢¢¢Представление информации в битахМанипуляции на уровне битЦелы姧§§§¢Представление: беззнаковое и знаковоеПреобразованияРасширение, сокращениеСложение, отрицание, умножение, сдвигСводкаПредставление в памяти, указатели, строки45Арифметика: основные правила¢Сложение:§ (Без)знаковые: Нормальное сложение с отсечением,идентичные действия с битами§ Беззнаковые: сложение по модулю 2w§ Математическое сложение и возможное уменьшение на 2w§ Знаковые: изменённое сложение по модулю 2w (результат вдопустимом диапазоне)§ Математическое сложение и возможное добавление илиуменьшение на 2w¢Умножение:§ (Без)знаковые: Нормальное умножение с отсечением, разныедействия с битами§ Беззнаковые: умножение по модулю 2w§ Знаковые: изменённое умножение по модулю 2w (результат вдопустимом диапазоне)46Зачем использовать беззнаковые?¢Не используйте без понимания последствий§ Легко сделать ошибкуunsigned i;for (i = cnt-2; i >= 0; i--)a[i] += a[i+1];§ Может быть очень коварным#define DELTA sizeof(int)int i;for (i = CNT; i-DELTA >= 0; i-= DELTA).

. .47Обратный отсчёт с беззнаковыми¢Правильно: счётчик цикла - беззнаковыйunsigned i;for (i = cnt-2; i < cnt; i--)a[i] += a[i+1];¢См. «Безопасное программирование на C и C++»,Роберт Сикорд, ISBN 978-5-8459-1908-3, «ВИЛЬЯМС», 2015§ Стандарт гарантирует, что беззнаковое сложение работает какматематическое сложение по модулю§ 0 – 1 à UMax¢Ешё лучшеsize_t i;for (i = cnt-2; i < cnt; i--)a[i] += a[i+1];§ Тип size_t определён как беззнаковый с длиной равной размеру слова§ Код работает даже если cnt = Umax§ А что если cnt – знаковый и < 0?48Зачем использовать беззнаковые? (ещё)¢Используйте для модулярной арифметики§ Арифметика произвольной точности¢Используйте для представления множеств§ Логический сдвиг вправо, без расширения знака49Биты, байты и целые¢¢¢Представление информации в битахМанипуляции на уровне битЦелы姧§§§¢Представление: беззнаковое и знаковоеПреобразованияРасширение, сокращениеСложение, отрицание, умножение, сдвигСводкаПредставление в памяти, указатели, строки50Байтовая организация памяти0•••00F•••FF•••¢Программы обращаются к виртуальным адресам§ Концептуально – очень большой массив байт§ В действительности реализуется иерархией запоминающих устройствразличного типа§ ОС предоставляет своё адресное пространство каждому «процессу»§ Программа исполняется в рамках своего «процесс໧ Программа может повредить только свои, но не чужие данные¢Компилятор, компоновщик, загрузчик и среда исполнения§ Определяют где хранятся различные программные объекты§ Выделяют память внутри единого адресного пространства51Машинные слова¢С машиной связан “размер слова”§ Обычный размер представления целых чиселВключая адреса§ Большинство мобильников ещё используют слова в 32 бита (4 байта)§ Предел адресации 4ГБ§ Недостаточно для интенсивной работы с памятью§ ПК и более мощные системы - используют слова в 64 бита (8 байт)§ Потенциальное адресное пространство ≈ 1.8 X 1019 байт§ Архитектура x86-64 использует 48-битовые адреса: 256 терабайт§ Машины поддерживают множество форматов данных§ Доли размера слова или кратные ему§ Всегда целое число байт§52Словная организация памяти¢Адреса указываютрасположение в байтах§ Адрес первого байта в слове§ Адреса последовательных словразличаются на 4 (32-битные) или8 (64-битные)32-бит.

64-бит.Байты Адресслова словаАдрес=0000??Адрес=0004??Адрес=0008??Адрес=0012??Адрес=0000??Адрес=0008??000000010002000300040005000600070008000900100011001200130014001553Целочисленные форматыТипы данныхязыка C32-биттипичноIntel IA32x86-64char111short222int444long448long long888указатель44854Порядок байт в слове¢¢В каком порядке располагаются в памятибайты многобайтового слова?Соглашения§ «Тупоконечники»: Sun, PPC Mac, InternetНаименее значимый байт имеет наибольший адрес§ «Остроконечники»: x86§ Наименее значимый байт имеет наименьший адрес§55Примеры упорядочения байт¢«Тупоконечно廧 Наименее значимый байт имеет наибольший адрес¢«Остроконечно廧 Наименее значимый байт имеет наименьший адрес¢Пример§ Переменная xимеет 4-байтовое представление 0x01234567§ Расположена по адресу &x - 0x100§«Тупоконечное»0x100 0x101 0x102 0x1030101«Остроконечное»2323454567670x100 0x101 0x102 0x103676745452323010156Десятичное:Представление Двоичное:Целочисленное Шестнадцатиричное:int A = 15213;IA32, x86-646D3B0000Sun00003B6Dint B = -15213;IA32, x86-6493C4FFFFSunFFFFC493152130011 1011 0110 11013B6Dlong int C = 15213;IA326D3B0000x86-646D3B000000000000Sun00003B6DДва представления в дополнительном коде(пояснения последуют)57Изучение представления данных¢Вывод байтового представления данных§ Представление указателя как массива unsigned char *typedef unsigned char *pointer;void show_bytes(pointer start, int len){int i;for (i = 0; i < len; i++)printf(”%p\t0x%.2x\n",start+i,start[i]);printf("\n");}Спецификации преобразования:%p:Вывод указателя%x:Вывод шестнадцатиричного58Пример исполненияshow_bytesint a = 15213;printf("int a = 15213;\n");show_bytes((pointer) &a, sizeof(int));Результат (x86, Linux):int a = 15213;0x11ffffcb8 0x6d0x11ffffcb9 0x3b0x11ffffcba 0x000x11ffffcbb 0x0059Представление указателейint B = -15213;int *P = &B;SunIA32x86-64EFD40CFFF889FBFFEC2CBFFFFF7F0000Различные компиляторы, ОС и машины дают различноерасположение в памяти60Представление строк¢Строки в Cchar S[6] = "18243";§ Представлены массивами сиволов§ Каждый символ представлен ASCII-кодомLinux/AlphaСтандартное 7-кодирование набора символов§ Символ “0” кодируется 0x30– Цифра i кодируется 0x30+i§ Строки должны завершаться нулевым кодом§ Символ окончания строки = 0§¢Совместимость§ ASCII-код не единственный§ Однобайтные коды не переупорядочиваютсяSun31313838323234343333000061Целочисленные головоломки CиДля каждого следующего выражения Си объясните почему оно…§ либо верно для любых значений аргументов,§ либо неверно.⇒ ((x*2) < 0)• x<0• ux >= 0⇒ (x<<30) < 0• x & 7 == 7• ux > -1⇒ -x < -y• x>yИнициализация• x * x >= 0⇒ x+y>0int x = function1();• x > 0 && y > 0⇒ -x <= 0• x >= 0int y = funciton2();⇒ -x >= 0• x <= 0unsigned ux = x;• (x|-x)>>31 == -1• ux >> 3 == ux/8unsigned uy = y;• x >> 3 == x/8• x & (x-1) != 0¢62.

Характеристики

Список файлов лекций