Как обрабатывать переполнение INT на ограниченных устройствах памяти (на любом языке)?

Question

У меня есть задача в школе, где я должен ответить на этот вопрос:

«Несколько учеников составляют программу календаря, где дни« абсолютный дневной номер »определяется как количество дней с 1 января года 0 до текущий день. На многих небольших компьютерах максимальное значение для Int составляет 32767. Что может случиться, если мы не будем этого делать? Как вы можете решить эту проблему? "

Вопрос типа меня смущает. В настоящее время я работаю на Python и из того, что я прочитал. Python автоматически обрабатывает переполнения Int, преобразовывая Int в Long, а другие языки программирования выполняют аналогичные вещи (например, обертывая отрицательное число, AKA 32768 становится -32767). Если языки программирования не автоматически обрабатывали переполнения, я бы предположил, что вы просто получите ошибку, если число переместится через 32767 ... правильно?

Если вы хотите напечатать «абсолютный дневной номер» (при условии, что он превышает 32767, и вы можете использовать только Int), вы не сможете, потому что вы не можете сохранить значение в Int. Это было бы невозможно. Если вы хотите просто распечатать сегодняшнюю дату, вы можете просто взять ее с ПК или использовать время Unix.

Для меня кажется, что ответ на этот вопрос зависит от того, что именно вы хотите, чтобы программа выполняла. Но мой учитель говорит «нет». Он говорит, что ни один из моих ответов не верен. Я не совсем понимаю, какой ответ он хочет, и это должно быть легким вопросом, так как я только программировал около 2 месяцев. Что мне не хватает, что так очевидно? Могу ли я это переусердствовать?

Answer 1

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

И это не имеет никакого отношения к ОЗУ.

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

То есть, число Maximun (в двоичной системе) можно хранить в:

1111 1111 1111 1111 

Итак, что происходит, когда мы добавляем 1 к этому?

1111 1111 1111 1111 
+0000 0000 0000 0001 

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

Итак, мы видим, что результат 65535 + 1 приводит к 0, что кажется неправильным. Но нам нужно привыкнуть к мысли, что целочисленная арифметика выполняется по модулю 2^n, где n - размер слова в битах. Правильный результат - 65536, а 65536 mod 2¹⁶ равен 0.

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

Итак, что может случиться, если вы проигнорируете это? Вы можете получить неправильные результаты.

Как вы можете это решить? Используйте два целых числа для представления чисел, которые не помещаются в одно целое. Есть много возможностей, как это сделать. Одной из возможностей, которая легко понять, но не идеальна в отношении эффективности памяти, будет следующее: представить количество дней в 2 целых числах. В первом целом мы подсчитываем только тысячи. Во втором мы представляем только последние 3 цифры (в десятичной нотации). Например, чтобы представить5, мы устанавливаем первое целое число в 432, второе - в 105.

Answer 2

ЦП не обнаруживает недопустимые результаты во всех условиях, поэтому вы должны сами проверить их. И тогда у вас все еще есть проблема, что математика не работает, и вы не можете выполнить расчет, который вы хотите. Альтернативное решение состоит в том, чтобы хранить данные в более крупной структуре данных и реализовывать свои собственные операции add/subtract/... в структуре.

Это то, что делает python, и поэтому он может хранить неопределенно большие целые числа изначально. Проверьте модуль decimal python для другого примера. Есть библиотеки для C/C++, и я предполагаю и другие языки. Вы также можете реализовать API самостоятельно - это немного утомительно, но выполнимо.