Как целые положительные и отрицательные числа представлены в памяти компьютера?

Обновлено: 04.07.2024

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

Подходы с фиксированным и переменным размером

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

Хранилище переменного размера выделяет столько битов, сколько необходимо для представления целочисленного значения. Подход аналогичен нашему обычному опыту написания десятичных целых чисел. Мы используем одну десятичную цифру (например, 1 или 7) для записи небольших целых чисел, две цифры (например, 12 или 65) для целых чисел от 10 до 99, три цифры (например, 123 или 948) для целых чисел от 100 до 999, и т. д. Такой подход допускает неограниченный диапазон целых чисел — до тех пор, пока у нас достаточно места для записи цифр.

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

Основные [беззнаковые] целочисленные типы C

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

Например, MyroC хранит изображения (например, с камеры) попиксельно. Каждый пиксель содержит значения красного, зеленого и синего, а переменная char (т. е. 1 байт) используется для хранения интенсивности каждого цвета. То есть текущий механизм хранения требует 3 байта для каждого пикселя.

• Для изображения среднего разрешения (800 x 1280 пикселей) требуется около 3 072 000 байт (3 МБ), если данные о цвете хранятся по 1 байту на каждый цвет на пиксель. Эксперименты показывают, что для передачи этих данных по Bluetooth требуется 25–30 секунд на каждое изображение.
• Если бы для каждого цвета использовалось 8 байтов (тип C long int или long long int, в зависимости от компьютера), для хранения одного изображения потребовалось бы около 24 МБ. а для передачи изображения по Bluetooth потребуется более 7 минут.

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

В общей сложности стандарт C 2011 определяет пять различных основных типов для хранения [беззнаковых] целых чисел. Кроме того, Стандарт указывает минимальное количество битов, необходимое для каждого целочисленного типа. Однако, поскольку компьютерная память со временем становится больше и дешевле, стандарт C 2011 позволяет использовать более крупные распределения битов, чем минимум. Запустите программу integer-sizes.c на вашем локальном компьютере, чтобы определить, сколько битов выделено для различных типов на вашем компьютере. Ниже приведены некоторые дополнительные примечания:

• Исторически тип char или тип unsigned char (1 байт) использовался для символьных данных, хотя char считается типом для небольших целых чисел. char будет обсуждаться более подробно в сегментах курса, сессиях, чтениях и лабораторных работах, связанных с символьными данными.
  • Традиционно символы ориентировались на западный алфавит, хотя доступны и другие варианты, и исторически для хранения этих символов требовался всего один байт.
  • Новые параметры символов позволяют использовать несколько байтов, а новые возможности определены в заголовке и библиотеке wchar.h.

  Типы C без знака

  Экскурсия: базовое дополнение

  Сложение двоичных чисел осуществляется по тем же правилам, что и сложение десятичных чисел:

  Складывая 1 + 1, думайте о 1 как о переносе на следующее место.

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

  Для иллюстрации мы добавляем 1 к 0 шесть раз:

  Дополнительная практика

  Целые числа со знаком

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

  • Если для целого числа выделено 16 бит, то целое число может хранить 2 16-битных шаблона, а переменная может содержать значения от 0 до 2 16 -1=65535.
  • Если выделено 32 бита, то целое число может хранить 2 32-битных шаблона, а переменная может содержать значения от 0 до 2 32 -1=4294967295.

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

  • Если для отрицательных и неотрицательных целых чисел выделено 16 бит, диапазон чисел будет примерно от -32 767 до 32 767.
  • Если выделено 32 бита, диапазон может быть от -2 147483647 до 2 147483647.

  Имея это в виду, C определяет две версии стандартных целых чисел:

  • Основные целочисленные типы (char, short int, int, long int, long long int) допускают отрицательные, нулевые и положительные значения.
  • Добавление "unsigned" к типу (unsigned char, unsigned short int, unsigned int, < tt>unsigned long int, unsigned long long int) предписывает, что все биты будут использоваться для представления неотрицательных целых чисел.

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

  Интересно, что стандарт C 2011 допускает три варианта представления отрицательных чисел.

  Диапазон целочисленных типов варьируется

  Запустите программу integer-ranges.c на локальном компьютере, чтобы определить диапазоны различных типов на вашем компьютере.

  Обозначение знак-величина

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

  • Если крайний левый бит равен 0, число неотрицательное.
  • Если крайний левый бит равен 1, число неположительно.

  Как мы обсудим, механизм определения представления отрицательного числа различается в зависимости от трех обозначений, но в каждом случае крайний левый бит эффективно указывает знак числа (- или +).

  С первым битом, посвященным знаку числа (- или +), наибольшее положительное число, которое может быть представлено, будет 0111. 111. То есть первый бит равен 0 (знак +), а остальные биты равны 1. Числа, превышающие это, не могут быть правильно сохранены — ситуация называется переполнением.

  В записи со знаком первый бит равен 0 или 1 (для + или - соответственно), а остальные биты задают двоичные биты неотрицательного числа.

  Примеры использования 16-битного целого числа со знаком:

  • Как показано в таблице, число ноль имеет два представления (+0 и -0).
  • При таком обозначении сложение несколько усложняется, так как нужно учитывать сложение двух положительных чисел, одного положительного и одного отрицательного, одного отрицательного и одного положительного и двух отрицательных.

  Оба этих обстоятельства (нуль, сложение) усложняют схему.

  Практика

  Заполните таблицу для 16-битного представления заданного десятичного целого числа со знаком-величиной

  Обозначение с дополнением до единицы

  Как и в случае записи величины знака с использованием n бит, все неотрицательные числа должны использовать правые биты n-1 и записываться с начальным нулем. Неотрицательные числа в точности совпадают с обозначениями величины знака и дополнения до единицы (а также с дополнением до двух, которые будут обсуждаться позже).

  Дано неотрицательное число, соответствующее отрицательное число определяется путем замены всех 0 на 1 и всех 1 на 0. Ниже приведены несколько примеров:

  Практика

  Заполните таблицу для 16-битного представления данного десятичного целого числа с дополнением до единицы

  Дополнение в единицы

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

  Рассмотрите двоичное сложение для ±87 и ±27. (Подходящие значения см. в приведенном выше примере.)

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

  • Число ноль имеет два представления (все нули и все единицы).
  • Пример со сложением предполагает, что иногда сложение работает нормально с нотацией с дополнением до единиц. Однако иногда происходит перенос в семнадцатую цифру, и когда семнадцатый бит удаляется, к вычисленной сумме необходимо добавить 1, чтобы получить правильный ответ.

  Опять же, обе формы нуля и множественные случаи сложения усложняют схему.

  Необязательно: для склонных к математике и/или любознательных

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

  Предположим, что для чисел с дополнением до единицы выделено n битов. Поскольку биты n допускают 2 n различных шаблонов — около половины для положительных и около половины для отрицательных (и 1 или 2 для нуля), положительные числа будут находиться в диапазоне от 0 до 2 n-1 -1.

  Кроме того, поскольку мы храним только n бит, мы можем добавлять или вычитать кратные 2 n по своему желанию — такие значения не сохраняются в n-битных числах.

  Теперь предположим, что a и b — положительные целые числа, 0 ≤ a, b ≤ 2 n-1 -1. Отрицательные числа -a и -b будут представлены двоичными значениями с первой единицей — числами от 2 n-1 -1 до 2 n .

  Далее рассмотрим процесс переключения битов с 0 на 1 и с 1 на 0. Одним из способов выполнить это переключение является вычитание исходного бита из 1:

  Положительное число, представляющее все n 1, равно 2 n -1, поэтому переключение всех битов a может быть достигнуто путем побитового вычитания двоичного представления a из 2 n -1. . То есть представление числа -a с дополнением до единицы задается числом 2 n -1 - a — числом с ведущей 1, которое больше, чем 2 n-1 -1. Точно так же -b представляется как 2 n -1 - b.

  Теперь давайте рассмотрим случаи арифметики; для простоты мы предполагаем b > a.

  a + b будет положительным. Пока это число может быть представлено n-1 битами, сложение будет работать без проблем.

  Рассмотрите варианты а–б. Поскольку мы предполагаем, что b > a, (b - a) положительно, а (a - b) отрицательно. Мы заметили, что -b будет представлено 2 n -1 - b, поэтому a - b = a - (2 n -1 - b) = (2 n -1 - (b - a)). В нотации с дополнением до единиц это значение точно соответствует -(b-a), как и требовалось.

  Рассмотрите -a - b. Поскольку -a представлено 2 n -1 - a и -b представлено 2 n -1 - b, -a -b представлено 2 n -1 - a + 2 n -1 - b = 2 * 2 n -2 - (а + б).

  Здесь множитель 2*2 n указывает на перенос в лишнюю цифру. Кроме того, член -2 отличается на единицу для дополнения до единицы. В целом, мы можем получить правильный результат, игнорируя перенос в лишнюю цифру и добавляя 1.

  Возьмем б - а. Поскольку -а представлено 2 n -1 - а, b - а представлено 2 n -1 - а + b. Поскольку мы предполагаем, что b > a, b-a положительно, ответом на сложение должно быть b-a. При интерпретации этого числа мы можем игнорировать 2 n (перенос в n-й бит), потому что это число не хранится в n битах. Это оставляет число -1 - a - b, которое отличается на 1. Опять же, добавление 1 к результату вычисления b-a дает правильный ответ.

  В целом, представление -a с помощью 2 n -1 - a иногда работает нормально, но иногда представление сбивается на 1, и нам нужен дополнительный член 2 n (не записанный), чтобы результат работал правильно.

  Обозначение с дополнением до двух

  Как и в других n-битовых обозначениях для отрицательных и неотрицательных целых чисел, крайний левый бит для неотрицательных целых чисел равен 0, целые числа используют оставшиеся n-1 биты и неотрицательные целые числа должны находиться в диапазоне от 0 до 2 n-1 -1.

  Также при наличии неотрицательного числа a запись с дополнением до двух для -a получается в два основных шага:

  1. Запишите -a в нотации с дополнением до единицы.
  2. Добавить 1

  Следует несколько примеров:

  Практика

  Заполните таблицу для 16-битного представления заданного десятичного целого числа с дополнением до двух

  Необязательно: для склонных к математике и/или любознательных

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

  Поскольку представление с дополнением до двух для -a начинается с обозначения с дополнением до единиц и добавляет единицу, представление с дополнением до двух для -a равно 2 n - a. С помощью этой записи полностью решены проблемы сложения чисел с дополнением до единицы (включая иногда отклонение на единицу).

  Заключительные замечания

  На практике запись с дополнением до двух имеет два преимущества перед другими подходами к представлению отрицательных целых чисел.

  • Изучая запись с дополнением до двух, обратите внимание, что добавление 1 к -0 в записи с дополнением до единицы дает 00000. 000, то же значение, что и +0. Таким образом, запись с дополнением до двух имеет только один битовый шаблон для числа ноль.
  • В примечаниях Для математически склонных или любознательных объясняется, почему сложение с дополнением до двух решает проблемы, возникающие при записи со знаком и величиной (сложность) и с записью с дополнением до единицы (дополнительный перенос и иногда отклонение на единицу). .

  В целом, несмотря на то, что стандарт C 2011 года разрешает использовать нотацию со знаком-величиной, нотацию с дополнением до единицы и нотацию с дополнением до пары, [почти] все современные компьютеры используют нотацию с дополнением до пары из-за ее простого представления нуля и его эффективность с добавлением целых чисел.

  Авторское право © 2011–2015 Генри М. Уокер.
  Избранные материалы защищены авторскими правами Мардж Коаран, Сэмюэля А. Ребельски, Джона Дэвида Стоуна и Генри Уокера и используются с их разрешения.
  Эта страница и другие материалы, разработанные для CSC 161, находятся в разработке.
  Это и все лабораторные упражнения для CSC 161 лицензированы в соответствии с международной лицензией Creative Commons Attribution-NonCommercial-Share Alike 4.0.

  Я пытаюсь понять, как Java хранит целые числа внутри себя. Я знаю, что все примитивные целые числа Java подписаны (кроме коротких?). Это означает, что в байте для числа доступно на один бит меньше.

  Мой вопрос: все целые числа (положительные и отрицательные) хранятся в виде дополнения до двух или это только отрицательные числа в дополнении до двух?

  Я вижу, что в спецификациях указано x бит два в дополнительном числе . Но я часто путаюсь.

  Изменить

  Для ясности, x = 15

  Итак, если ваш ответ: все числа хранятся в виде дополнения до двух, то:

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

  Изменить Не уверен, что мой вопрос сбивает с толку. Вынужден изолировать вопрос:

  Точно мой вопрос: сохраняются ли положительные числа в двоичном формате как есть, а отрицательные числа хранятся в виде дополнения до двух?

  Некоторые говорят, что все они хранятся в дополнении до двух, а в одном ответе говорится, что в дополнении до двух хранятся только отрицательные числа.

  10 ответов 10

  Начнем с суммирования примитивных типов данных Java:

  Short: тип данных Short представляет собой 16-битное целое число в дополнении до двух со знаком.

  int: тип данных Int представляет собой 32-разрядное целое число в дополнении до двух со знаком.

  long: тип данных Long представляет собой 64-битное целое число в дополнении до двух со знаком.

  float: тип данных с плавающей запятой представляет собой 32-разрядное число с плавающей запятой одинарной точности IEEE 754.

  double: тип данных double представляет собой 64-разрядную двойную точность с плавающей запятой IEEE 754.

  boolean: логический тип данных представляет один бит информации.

  char: тип данных char — это один 16-битный символ Unicode.

  Дополнение до двух

  "Хорошим примером из вики является то, что связь с дополнением до двух реализуется за счет того, что 256 = 255 + 1, а (255 − x) – это дополнение x до единиц

  0000 0111=7 дополнение до двух равно 1111 1001= -7

  это работает так, что MSB (самый значащий бит) получает отрицательное значение, поэтому в случае выше

  Положительные целые числа обычно хранятся в виде простых двоичных чисел (1 — это 1, 10 — это 2, 11 — это 3 и т. д.).

  Отрицательные целые числа хранятся в виде дополнения до двух от их абсолютного значения. Дополнение до двух положительного числа при использовании этой записи является отрицательным числом.

  Поскольку я получил несколько баллов за этот ответ, я решил добавить к нему больше информации.

  Более подробный ответ:

  Среди прочего существует четыре основных подхода к представлению положительных и отрицательных чисел в двоичном формате, а именно:

  1. Величина со знаком
  2. Комплементация
  3. Дополнение до двух
  4. Предвзятость
  <р>1. Величина со знаком

  Старший бит используется для представления знака, остальные биты используются для представления абсолютного значения. Где 0 представляет положительное число, а 1 представляет отрицательное число, например:

  Это представление проще. Однако вы не можете добавлять двоичные числа так же, как десятичные числа, что усложняет реализацию на аппаратном уровне. Кроме того, этот подход использует два двоичных шаблона для представления 0, -0 (1000) и +0 (0000).

  <р>2. Дополнение к одному

  В этом представлении мы инвертируем все биты заданного числа, чтобы найти его дополнительные. Например:

  Проблема с этим представлением заключается в том, что по-прежнему существуют два битовых шаблона для представления 0, отрицательного 0 (1111) и положительного 0 (0000)

  <р>3. Дополнение до двух

  Чтобы найти отрицательное число, в этом представлении мы инвертируем все биты, а затем добавляем один бит. Добавление одного бита решает проблему наличия двух битовых шаблонов, представляющих 0. В этом представлении у нас есть только один шаблон для 0 (0000).

  Например, мы хотим найти двоичное отрицательное представление числа 4 (десятичное), используя 4 бита. Сначала мы преобразуем 4 в двоичное:

  затем инвертируем все биты

  наконец, мы добавляем один бит

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

  Более быстрый способ найти комплементарность — зафиксировать первый бит равным 1 и инвертировать оставшиеся биты. В приведенном выше примере это будет что-то вроде:

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

  <р>4. Предвзятость

  Это представление используется для представления экспоненты в норме IEEE 754 для чисел с плавающей запятой. Его преимущество состоит в том, что двоичное значение, в котором все биты равны нулю, представляет наименьшее значение. И двоичное значение со всеми битами до 1 представляет собой самое большое значение. Как следует из названия, значение закодировано (положительное или отрицательное) в двоичном формате с n битами со смещением (обычно 2^(n-1) или 2^(n-1)-1).

  Поэтому, если мы используем 8 бит, десятичное значение 1 представляется в двоичном виде со смещением 2^(n-1) значением:

  Если этот диапазон недостаточно велик для обработки предполагаемых значений, необходимо использовать больший размер. Например, слово (16 бит) может использоваться для представления \(2^\) или 65 536 различных значений, а двойное слово (32 бита) может использоваться для представления \(2^\) или 4 294 967 296 различных значений. числа. Таким образом, если вы хотите сохранить значение 100 000, потребуется двойное слово.

  Как вы помните из C, C++ или Java, целочисленное объявление (например, int ) — это одно двойное слово, которое можно использовать для представления значений между \(-2^\) (−2 147 483 648) и + \(2^\) - 1 (+2 147 483 647).

  В следующей таблице показаны диапазоны, связанные со стандартными размерами:

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

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

  Например, диапазон байтов без знака может быть представлен с помощью числовой строки следующим образом:

  
  < /p>

  Например, диапазон байтов со знаком также может быть представлен с помощью числовой строки следующим образом:

  
  < /p>

  То же самое относится к полусловам и словам с большим диапазоном значений.

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

  Например, когда значения без знака и со знаком находятся в перекрывающемся положительном диапазоне (от 0 до +127):

  • Байтовое представление \(12_\) со знаком равно 0x0\(C_\)
  • Байтовое представление \(-12_\) также равно 0x0\(C_\)

  Когда значения без знака и со знаком выходят за пределы перекрывающегося диапазона:

  • Байтовое представление \(-15_\) со знаком равно 0x\(F1_\)
  • Байтовое представление \(241_\) также равно 0x\(F1_\)

  Это совпадение может вызвать путаницу, если типы данных не определены четко и правильно.

  Дополнение до двух

  Ниже описано, как найти представление дополнения до двух для отрицательных значений (не положительных значений).

  Чтобы получить дополнение числа до двух:

  1. дополнить единицу (отрицать)
  2. добавить 1 (в двоичном формате)

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

  Пример

  9 (8 + 1) =	00001001
  Шаг 1	11110110
  Шаг 2	11110111
  -9 (в шестнадцатеричном формате)	F7

  < td >-12 (в шестнадцатеричном формате)

  12 (8 + 4) =	00001100< /td>
  Шаг 1	11110011
  11110100
  F4

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

  Пример

  Чтобы найти размер слова (16 бит), используйте представление в дополнении до двух от -18 и -40.

  18 (16 + 2) =	0000000000010010
  Шаг 1	1111111111101101
  Шаг 2	1111111111101110
  -18 (hex)	0xFFEE

  40 (32 + 8) =	0000000000101000
  Шаг 1	1111111111010111
  Шаг 2	11111111111011000
  -40 (hex)	0xFFD8

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

  Вклады и атрибуции

  Эта страница находится под лицензией CC BY-NC-SA, ее автором, ремиксом и/или куратором выступил Эд Йоргенсен. Подробная история версий изменений исходного контента доступна по запросу.

  Прочитайте эти разделы о представлении целых и действительных чисел. Ранее вы читали о системах счисления и представлении чисел, используемых для вычислений. Это даст вам возможность просмотреть этот материал. Архитектура компьютера включает компоненты, которые выполняют функции хранения данных, передачи данных от одного компонента к другому, вычислений и взаимодействия с внешними по отношению к компьютеру устройствами. Данные хранятся в виде единиц, называемых словами. Слово состоит из ряда битов, обычно, в зависимости от компьютера, 32 бита или 64 бита. Слова продолжают становиться длиннее, с большим количеством битов. Инструкции также хранятся в словах. Ранее вы видели примеры того, как инструкции хранятся в слове или словах. Теперь вы увидите, как числа хранятся в словах.

  Целые числа

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

  Целые числа обычно хранятся в 16, 32 или 64 битах, причем 16-битное становится все реже, а 64-битное — все чаще. Основная причина этого увеличения заключается не в изменении характера вычислений, а в том, что для индексации массивов используются целые числа. По мере роста размера наборов данных (в частности, при параллельных вычислениях) требуются более крупные индексы. Например, в 32 битах можно хранить числа от нуля до . Другими словами, 32-битный индекс может адресовать 4 гигабайта памяти. До недавнего времени этого было достаточно для большинства целей; в наши дни потребность в больших наборах данных привела к необходимости 64-битной индексации.

  Когда мы индексируем массив, нужны только положительные целые числа. В общих целочисленных вычислениях, конечно, нам также необходимо учитывать и отрицательные целые числа. Существует несколько способов реализации отрицательных целых чисел. Самое простое решение — зарезервировать один бит в качестве знакового бита, а оставшиеся 31 (или 15, или 63; с этого момента мы будем считать стандартом 32 бита) использовать оставшиеся 31 бит для хранения абсолютной величины.< /p>

  
  < бр />

  У этой схемы есть некоторые недостатки, один из которых заключается в том, что в ней есть как положительное, так и отрицательное число ноль. Это означает, что проверка на равенство становится более сложной, чем простая проверка на равенство в виде строки битов.

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

  • Если , используется обычный битовый шаблон для m.
  • Если , то представлен битовым шаблоном для .

  
  < /p>

  Некоторые наблюдения:

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

  Упражнение 3.1. Для «наивной» схемы и схемы с дополнением до 2 для отрицательных чисел дайте псевдокод для сравнительного теста m и давайте посмотрим, что происходит при вычислении .

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

  • Случай: . Так как и является допустимым битовым шаблоном. Кроме того, это представление отрицательного числа в виде битового шаблона , поэтому мы действительно можем выполнять вычисления как беззнаковую операцию над строковыми представлениями m и n.
  • Случай: . Здесь мы это наблюдаем. Так как это число и, следовательно, не является законным выражением отрицательного числа. Однако если мы сохраним это число в 33 бита, мы увидим, что это правильный результат плюс один бит в 33-й позиции.Таким образом, выполняя сложение без знака и игнорируя бит переполнения, мы снова получаем правильный результат.
    

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

  Представление действительных чисел

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

  Вещественные числа хранятся по схеме, аналогичной так называемой "научной нотации", где число представлено как значащее и показатель степени, для Экземпляр 6.022 x 10 23 , который имеет значащие 6.022 с точкой основания после первой цифры и показателем степени 23. Это число обозначает

  Мы вводим основание, маленькое целое число, 10 в предыдущем примере и 2 в числах компьютеров, и записываем числа в его терминах в виде суммы t членов:

  где находятся компоненты

  • бит знака: один бит, определяющий, является ли число положительным или отрицательным;
  • является основой системы счисления;
  • цифры мантиссы или значащие – расположение точки счисления (десятичной точки в десятичных числах) неявно предполагается сразу после первой цифры;< /li>
  • t – длина мантиссы;
  • показатель степени; обычно и

  Обратите внимание, что для целого числа существует явный бит знака; знак экспоненты обрабатывается по-разному. Из соображений эффективности e не является числом со знаком; вместо этого оно рассматривается как число без знака, превышающее определенное минимальное значение. Например, битовый шаблон для числа ноль интерпретируется как e = L.
  

  Некоторые примеры

  Давайте рассмотрим некоторые конкретные примеры представлений с плавающей запятой. Основание 10 — наиболее логичный выбор для потребления человеком, но компьютеры бинарны, поэтому здесь преобладает основание 2. Старые мейнфреймы IBM группировали биты для представления в шестнадцатеричном формате.

  
  
  

  Из них наиболее распространены форматы одинарной и двойной точности. Мы обсудим их в разделе 3.2.4 и далее.
  

  Двоично-десятичный

  Десятичные числа неприменимы в научных вычислениях, но они полезны в финансовых расчетах, где расчеты, связанные с деньгами, должны быть точными. Двоичная арифметика здесь находится в невыгодном положении, поскольку такие числа, как 1/10, являются повторяющимися дробями в двоичном формате. При конечном числе битов в мантиссе это означает, что число 1/10 не может быть точно представлено в двоичном виде. По этой причине в старых мейнфреймах IBM использовались двоично-десятичные схемы, которые фактически стандартизируются в редакциях IEEE754 [4]; см. также раздел 3.2.4. Немногие процессоры в наши дни имеют аппаратную поддержку BCD; одним из примеров является IBM Power6.

  В схемах BCD одна или несколько десятичных цифр кодируются несколькими битами. Самая простая схема будет кодировать цифры 0 . . . 9 в четырех битах. Преимущество этого заключается в том, что в двоично-десятичном коде каждая цифра легко идентифицируется; его недостаток в том, что около 1/3 всех битов тратится впустую, поскольку 4 бита могут кодировать числа 0 . . . 15. Более эффективные кодировки будут кодировать 0 . . . 999 в десяти битах, что в принципе может хранить числа 0 . . . 1023. Хотя это эффективно в том смысле, что теряется несколько битов, идентификация отдельных цифр в таком числе требует некоторого декодирования.

  Тройные компьютеры

  Было проведено несколько экспериментов с тернарной арифметикой [2, 8, 9].

  Ограничения

  Поскольку мы используем только конечное количество битов для хранения чисел с плавающей запятой, не все числа могут быть представлены. Те, которые не могут быть представлены, делятся на две категории: слишком большие или слишком маленькие (в каком-то смысле) и те, что попадают в пробелы. Числа могут быть слишком большими или слишком маленькими по следующим причинам.

  Переполнение: наибольшее число, которое мы можем сохранить, равно , а наименьшее число (в абсолютном смысле) равно ; все, что больше первого или меньше второго, вызывает состояние, называемое переполнением.

  Недополнение: ближайшее к нулю число равно . Вычисление, результат которого меньше (по абсолютной величине), вызывает состояние, называемое потерей значимости. Фактически, большинство компьютеров используют нормализованные числа с плавающей запятой: первая цифра d₁ считается отличной от нуля; см. раздел 3.2.3 для получения дополнительной информации об этом. В этом случае любое число меньше вызывает недополнение.Попытки вычислить меньшее число иногда обрабатываются с помощью ненормализованных чисел с плавающей запятой (процесс, известный как постепенная потеря значимости), но обычно это в десятки или сотни раз медленнее. чем вычисления с обычными числами с плавающей запятой. На момент написания этой статьи только IBM Power6 имел аппаратную поддержку постепенной потери значимости.

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

  Нормализованные числа и машинная точность

  Общее определение чисел с плавающей запятой, уравнение (3.1), оставляет нас с проблемой, что числа имеют более одного представления. Например, . Поскольку это излишне усложнило бы компьютерную арифметику, например, при проверке равенства чисел, мы используем нормализованные числа с плавающей запятой. Число нормализовано, если его первая цифра отлична от нуля. Подразумевается, что часть мантиссы равна .

  Практическое значение в случае двоичных чисел заключается в том, что первая цифра всегда равна 1, поэтому нам не нужно хранить ее явно. В стандарте IEEE 754 это означает, что каждое число с плавающей запятой имеет форму

  Теперь мы можем уточнить ошибку представления. Номер машины — это представление всех x в интервале вокруг него. С t цифрами в мантиссе это интервал чисел, которые отличаются от x t + 1-й цифрой. Для части мантиссы мы получаем:

  
  

  Рисунок 3.1. Арифметика одинарной точности

  Машинную точность можно определить по-другому: это наименьшее число, которое можно прибавить к 1, чтобы 1 + имел представление, отличное от 1. Небольшой пример показывает, как выравнивание показателей степени может сдвинуть слишком маленький операнд, чтобы он эффективно игнорируется в операции сложения:

  
  
  

  Еще один способ взглянуть на это — заметить, что если отношение x и y слишком велико, результат будет идентичен х.

  Машинная точность — это максимально достижимая точность вычислений: не имеет смысла требовать точности более 6 или около того цифр в одинарной точности или 15 — в двойной.

  Упражнение 3.3. Напишите небольшую программу, которая вычисляет машинный эпсилон. Есть ли какая-то разница, если вы установите низкий или высокий уровень оптимизации компилятора? Можете ли вы найти другие причины, по которым это вычисление может пойти не так?

  Стандарт IEEE 754 для чисел с плавающей запятой

  Несколько десятилетий назад такие вопросы, как длина мантиссы и поведение операций округления, могли отличаться у разных производителей компьютеров и даже у моделей одного производителя. Очевидно, это была плохая ситуация с точки зрения переносимости кодов и воспроизводимости результатов. Стандарт IEE 754 2 кодифицировал все это, например, предписывая 24 и 53 бита для мантиссы в арифметике с одинарной и двойной точностью, используя последовательность хранения знакового бита, экспоненты, мантиссы. Это, например, облегчает сравнение чисел.

  Стандарт также объявил поведение округления «точным округлением»: результатом операции должна быть округленная версия точного результата.

  Выше (раздел 3.2.2) мы видели явления переполнения и потери значимости, то есть операции, приводящие к непредставимым числам. Существует еще одна исключительная ситуация, с которой необходимо разобраться: какой результат должен быть возвращен, если программа запрашивает недопустимые операции, такие как ? Стандарт IEEE 754 имеет для этого два специальных значения: Inf и NaN для «бесконечности» и «не числа». Если в выражении появляется NaN, все выражение будет оцениваться как это значение. Правило для вычислений с Inf немного сложнее [43].

  Перечень значений всех битовых комбинаций двойной точности IEEE 754 приведен на рис. 3.1. Обратите внимание, что для нормализованных чисел первой отличной от нуля цифрой является 1, которая не сохраняется, поэтому битовая комбинация интерпретируется как

  В настоящее время почти все процессоры соответствуют стандарту IEEE 754, за редкими исключениями. Например, графические процессоры Nvidia Tesla не соответствуют стандартам одинарной точности. Обоснованием этого является то, что двойная точность — это «научный» режим, а одинарная точность, скорее всего, используется для графики, где точное соответствие не имеет большого значения.

  Читайте также:

    
  • Как долго работает батарея на материнской плате
    
  • Samsung scx 4100 как сканировать на компьютер
    
  • Как зарегистрироваться в ego kz с мобильного телефона с ЭЦП
    
    
  • Как восстановить поврежденный файл mov с видеорегистратора