ДС20в02-представление-целых (1238923)
Текст из файла
Представление целыхОсновы информатикиКомпьютерные основы программированияu.to/DbCmFAНа основе CMU 15-213/18-243:Introduction to Computer Systemsu.to/XoKmFAЛекция 2, 17 февраля, 2020Лектор:Дмитрий Северов, кафедра информатики 608 КПМdseverov@mail.mipt.rucs.mipt.ru/wp/?page_id=3461Биты, байты и целые¢¢¢Представление информации в битахМанипуляции на уровне битЦелы姧§§§¢Представление: беззнаковое и знаковоеПреобразованияРасширение, сокращениеСложение, отрицание, умножение, сдвигСводкаПредставление в памяти, указатели, строки2(почти) Всё есть биты¢¢Каждый бит есть 0 или 1По разному кодируя/интерпретируя наборы бит§ Компьютеры определяют действия (инструкции)§ … представляют, и обрабатывают числа, множества, строки…¢Почему биты? Из-за электронной реализации§ Просто хранить с помощью двустабильных элементов§ Надёжно передаются по плохим и зашумленным проводникам0101.1V0.9V0.2V0.0V3Двоичный пример¢Представление чисел в двоичной системе§ 1521310 = 111011011011012§ 1.2010= 1.0011001100110011[0011]…2§ 1.5213 X 104 = 1.11011011011012 X 2134Кодирование значений байта¢Байт = 8 бит§ Двоичное от 000000002 до 111111112§ Десятичное: от 010 до 25510§ Шестнадцатиричное от 0016 до FF16Представление 16 цифр§ Используем символы от ‘0’ до ‘9’ и от ‘A’ до ‘F’§ Запись FA1D37B16 в Cи как– 0xFA1D37B– 0xfa1d37b§очнеирти еац но о еда тич чннт яиес ес воШ Д Д0 0 00001 1 00012 2 00103 3 00114 4 01005 5 01016 6 01107 7 01118 8 10009 9 1001A 10 1010B 11 1011C 12 1100D 13 1101E 14 1110F 15 11115Пример представления данных32-биттипично64-bitтипичноx86-64char111short222int444long488указатель488Тип даных языка C6Биты, байты и целые¢¢¢Представление информации в битахМанипуляции на уровне битЦелы姧§§§¢Представление: беззнаковое и знаковоеПреобразованияРасширение, сокращениеСложение, отрицание, умножение, сдвигСводкаПредставление в памяти, указатели, строки7Булева алгебра¢Предложена Джорджем Булем в XIX веке§ Алгебраическое представление одной из логик§Кодирует “Истина” как 1 и “Ложь” как 0И (And)nA&B = 1 когда оба A=1 and B=1НЕ(Not)nИЛИ (Or)~A = 1 when A=0nA|B = 1 когда либо A=1, либо B=1Исключающее ИЛИ (Xor)nA^B = 1 когда либо A=1, либо B=1, но не оба8Обобщение булевой алгебры¢Операции на битовых наборах (векторах)§ Операции выполняются побитово0110100101101001& 01010101 | 0101010101000001011111010100000101111101¢01101001^ 010101010011110000111100~ 010101011010101010101010Применимы все выводы булевой алгебры9Представление и операции с множествами¢Представление§ Вектор бит размером w представляет подмножество {0, …, w–1}§ aj = 1 если j ∈ A§01101001§ 76543210{ 0, 3, 5, 6 }01010101§ 76543210{ 0, 2, 4, 6 }§¢Операци觧§§&|^~ПересечениеОбъединениеРазностьДополнение01000001011111010011110010101010{ 0, 6 }{ 0, 2, 3, 4, 5, 6 }{ 2, 3, 4, 5 }{ 1, 3, 5, 7 }10Побитовые операции в языке Cи¢Операции &, |, ~, ^ доступные в Cи§ Применимы к любому “целостному” типу данных§long, int, short, char, unsigned§ Аргументы рассматриваются как вектора битов§ Каждый бит – независимый аргумент¢Примеры (тип данных сhar)§ ~0x41 ⇒ 0xBE~010000012 ⇒ 101111102§ ~0x00 ⇒ 0xFF§ ~000000002 ⇒ 111111112§ 0x69 & 0x55 ⇒ 0x41§ 011010012 & 010101012 ⇒ 010000012§ 0x69 | 0x55 ⇒ 0x7D§§011010012 | 010101012 ⇒ 01111101211Сравните: логические операции в C¢Логические операторы§ &&, ||, !0 кодирует “False”§ Всё, что не 0 кодирует “True”§ Всегда выдаёт 0 или 1§ Раннее завершение вычисления выражения§¢Примеры (тип данных char)§ !0x41 ⇒§ !0x00 ⇒§ !!0x41 ⇒0x000x010x01§ 0x69 && 0x55 ⇒ 0x01§ 0x69 || 0x55 ⇒ 0x01§ p && *p (способ избежать обращения по нулевому указателю)12Сравните: логические операции в C¢Логические операторы§ &&, ||, !0 кодирует “False”§ Всё, что не 0 кодирует “True”§ Всегда выдаёт 0 или 1§ Раннее завершение вычисления выражения§Внимание!¢ Примеры (тип данных char)&&вместо&(и||вместо|)…§ !0x41 ⇒ 0x00частых ошибок§ одна!0x00 из⇒ самых0x01§ программирования!!0x41 ⇒ 0x01на C§ 0x69 && 0x55 ⇒ 0x01§ 0x69 || 0x55 ⇒ 0x01§ p && *p (способ избежать обращения по нулевому указателю)13Операции сдвига в Си¢¢Сдвиг влево:x << yАргумент x01100010§ Сдвигает вектор битов x влево на y позиций<< 300010000– Вытолкнутые слева биты теряются§ Заполняет нулями справаЛогич.
>> 200011000Ариф. >> 200011000Аргумент x10100010<< 300010000Логич. >> 200101000Ариф. >> 211101000Сдвиг вправо:x >> y§ Сдвигает вектор битов x вправо на y позицийВытолкнутые справа биты теряются§ Логический сдвиг§ Заполняет нулями справа§ Арифметический сдвиг§ Повторяет вправо наиболее значимый бит§¢Неопределённый результат§ Сдвиг на величину меньше 0 или больше размера слова14Биты, байты и целые¢¢¢Представление информации в битахМанипуляции на уровне битЦелы姧§§§¢Представление: беззнаковое и знаковоеПреобразованияРасширение, сокращениеСложение, отрицание, умножение, сдвигСводкаПредставление в памяти, указатели, строки15Кодирование целочисленных значенийБеззнаковыхw−1B2U(X) =ix⋅2∑ii=0В дополнительном кодеB2T (X) = −xw−1 ⋅ 2 w−1 + ∑ xi ⋅ 2 ishort int x = 15213;short int y = -15213;¢Cи short длиной в 2 байтаi=0знаковыйбитДесятичное ШестнадцатиричноеДвоичное3B 6D 00111011 0110110115213C4 93 11000100 10010011-15213xy¢w−2Знаковый бит§ В дополнительном коде, наиболее значимый бит обозначает знак0 для неотрицательных§ 1 для отрицательных§16Пример кодирования (продолжение)x =y =Вес$1$2$4$8$16$32$64$128$256$512$1024$2048$4096$8192$16384$)32768$Итого:&15213: 00111011 01101101-15213: 11000100 1001001115213$1$1$0$0$1$4$1$8$0$0$1$32$1$64$0$0$1$256$1$512$0$0$1$2048$1$4096$1$8192$0$0$0$0$&15213&)15213$1$1$1$2$0$0$0$0$1$16$0$0$0$0$1$128$0$0$0$0$1$1024$0$0$0$0$0$0$1$16384$1$ )32768$& +15213&17Границы представления в W бит¢Беззнаковые значения§ UMin= 0¢000…0§ UMax=2wЗначения в дополнительном коде§ TMin=–2w–1100…0–1§ TMax111…1=2w–1 – 1011…1¢Другие значения§ минус 1111…1Значения для W = 16Десятичные ШестнадцатиричныеUMaxFF FF65535TMax7F FF32767TMin80 00-32768-1FF FF-1000 000Двоичные11111111 1111111101111111 1111111110000000 0000000011111111 1111111100000000 0000000018Значения для разных размеров словаWUMaxTMaxTMin¢8255127-1281665,53532,767-32,768324,294,967,2952,147,483,647-2,147,483,648Важно!§ |TMin | =TMax + 1§ Границы несимметричны§ UMax = 2 * TMax + 1¢6418,446,744,073,709,551,6159,223,372,036,854,775,807-9,223,372,036,854,775,808Программирование на Cи§ #include <limits.h>§ Объявленные константы, e.g.,§ ULONG_MAX§ LONG_MAX§ LONG_MIN§ Значения констант зависят отплатформы19Беззнаковые и знаковые величиныX0000000100100011010001010110011110001001101010111100110111101111B2U(X)0123456789101112131415B2T(X)01234567–8–7–6–5–4–3–2–1¢Совпадение§ Одинаковые кодировкинеотрицательных величин¢Взаимная однозначность§ Каждая комбинация битпредставляет своё значение числа§ Каждое представимое целое имеетуникальную кодировку¢Отображения обратимы§ ∀x, U2B(B2U-1 (x)) = xбиты беззнаковых§ ∀x, T2B(B2T-1 (x)) = x§ биты знаковых вдополнительном коде§20Биты, байты и целые¢¢¢Представление информации в битахМанипуляции на уровне битЦелы姧§§§¢Представление: беззнаковое и знаковоеПреобразованияРасширение, сокращениеСложение, отрицание, умножение, сдвигСводкаПредставление в памяти, указатели, строки21Соответствие знаковых и беззнаковыхЗнаковое в доп.кодеxБеззнаковоеT2UT2BXB2UuxНабор бит не меняетсяБеззнаковоеuxU2TU2BXB2TЗнаковое в доп.кодеxНабор бит не меняется¢Соответствие знаковых в доп.коде и беззнаковых:Сохраняем битовое представление и переинтерпретируем22Соответствие знаковых и беззнаковыхБитыЗнаковоеБеззнаковое0000000001110010220011330100440101501106011171000-881001-791010-6101011-5111100-4121101-3131110-2141111-115T2UU2T56723Соответствие знаковых и беззнаковыхБитыЗнаковоеБеззнаковое00000000011100102200113010040101550110660111771000-881001-791010-61011-51100-4121101-3131110-2141111-115=+/-2434101124Связь между знаковыми и беззнаковымиЗнаковое в доп.кодеxБеззнаковоеT2UT2BXB2UuxНабор бит не меняетсяw–1ux + + +x - ++0•••+++•••+++самый отрицательный битодиноко становитсясамым положительным25Визуализация преобразования¢Дополнительный ⇒ беззнаковый§ Инверсия взаимного положения§ Отрицательные ⇒ большие положительныеTMaxДиапазон знаковыхв дополнительном коде0–1–2UMaxUMax – 1TMax + 1 ДиапазонTMaxбеззнаковых0TMin26Знаковые и беззнаковые в Cи¢Константы§ По умолчанию целочисленные десятичные считаются знаковыми§ Беззнаковые обозначаются суффиксом “U”0U, 4294967259U¢Преобразование§ Явноеint tx, ty;unsigned ux, uy;tx = (int) ux;uy = (unsigned) ty;§ Неявное преобразование также происходит в вызовах процедур,арифметике, сравнениях, присваиванияхtx = ux;uy = ty;27Неожиданные преобразования¢Вычисления выражений§ При смешивании знаковых и беззнаковых,знаковые неявно преобразуются в беззнаковые§ Включая операции сравнения <, >, ==, <=, >=§ Пример для W = 32: TMIN = -2,147,483,648 , TMAX = 2,147,483,647¢Константа100-1-1-1-1214748364721474836472147483647U2147483647U-1-1(unsigned)-1(unsigned) -12147483647214748364721474836472147483647Константа2ИтогТип рез-та0U0U000U0U-2147483647-1-2147483648-2147483647-1-2147483648-2-2-2-22147483648U2147483648U(int)2147483648U(int) 2147483648U==unsigned<>signedunsigned>signed<>unsignedsigned>unsigned<>unsignedsigned28Сводка: преобразованиеЗнаковые ↔ Беззнаковые: правила¢¢¢¢Битовые последовательности сохраняются…… но интерпретируются по разномуВозможная неожиданность: добавление иливычитание 2wВ выражениях содержащих signed int и unsigned int§ [signed] преобразуются в unsigned !!29Биты, байты и целые¢¢¢Представление информации в битахМанипуляции на уровне битЦелы姧§§§¢Представление: беззнаковое и знаковоеПреобразованияРасширение, сокращениеСложение, отрицание, умножение, сдвигСводкаПредставление в памяти, указатели, строки30Расширение знака¢Задача:§ Дано знаковое целое x размером w бит§ Преобразовать в целое того же значения размером w+k бит¢Правило:§ Сделать k копий знакового бита:§ Xʹ = xw–1 ,…, xw–1 , xw–1 , xw–2 ,…, x0k копий MSbXw••••••X′•••k•••w31Пример расширения знакаshort int x = 15213;intix = (int) x;short int y = -15213;intiy = (int) y;xixyiy¢¢Десятич.Шестнадцатир.152133B 6D15213 00 00 3B 6D-15213C4 93-15213 FF FF C4 93Двоичное0011101100000000 00000000 001110111100010011111111 11111111 1100010001101101011011011001001110010011Преобразование из короткого в длинный целочисленный типCи автоматически выполняет расширение знака32Сводка:Расширение, усечение: правила¢Расширение (например, short int в int)§ Беззнаковое: добавить нули§ Знаковое: расширить знак§ Оба действия дают ожидаемый результат¢Усечение (например, unsigned в unsigned short)§§§§§Unsigned/signed: биты отбрасываютсяРезультат переинтепретируется для новой длиныUnsigned: операция «остаток от деления»Signed: операция похожая на «остаток от деления»Ожидаемый результат – только для малых значений.33Биты, байты и целые¢¢¢Представление информации в битахМанипуляции на уровне битЦелы姧§§§¢Представление: беззнаковое и знаковоеПреобразованияРасширение, сокращениеСложение, отрицание, умножение, сдвигСводкаПредставление в памяти, указатели, строки34Беззнаковое сложениеu•••+ vu+v•••UAddw(u , v)•••Операнды: w битПолная сумма: w+1 битБез переноса: w бит¢•••Стандартная операция сложения в Си§ «Игнорирует» перенос§ Реализует сложение по модулюs =UAddw(u , v)=(u + v) mod 2w35Математическое сложение визуально¢Сложение целыхAdd4(u , v)§ 4-х битовые целые u, v§ Полная сумма Add4(u , v)§ Значение растёт линейнопо u и v§ Образует плоскостьInteger Addition32282420161412121088460042u46v28101201436Беззнаковое сложение визуально¢ПереполнениеУсечение§ Если полная сумма ≥ 2w§ Не более одного разаПолная сумма2w+1 ПереполнениеUAdd4(u , v)1614121082w1461210408260Сумма по модулю0u4246v28101201437Сложение в дополнительном кодеОперанды: w битПолная сумма: w+1 ,битБез преноса: w бит¢u•••+ vu+v•••TAddw(u , v)••••••TAdd и UAdd преобразуют биты одинаково§ Знаковое и беззнаковое сложение в Cи:int s, t, u, v;s = (int) ((unsigned) u + (unsigned) v);t = u + v§ Всегда даст s == t38Переполнение TAdd¢Полная суммаФункциональность§ Полное суммированиетребует w+1 бит§ Отбрасывание MSB§ Интерпретацияоставшихся бит какцелого числа вдополнительном коде0 111…12w–1+ПереполнениеРезульат TAdd0 100…02w –10 000…00000…01 011…1–2w –1–1100…01 000…0–2w011…1-Переполнение39Сложение в доп.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
