Как обнаружить переполнение кратного числа без знака? - PullRequest
Новая
       78

Как обнаружить переполнение кратного числа без знака?

571 голосов
/ 14 октября 2008

Я писал программу на C ++, чтобы найти все решения a b = c , где a , b и c вместе используют все цифры 0-9 ровно один раз. Программа зациклилась на значениях a и b , и каждый раз запускала процедуру подсчета цифр на a , b и a b для проверки выполнения условия цифр.

Однако ложные решения могут быть сгенерированы, когда a b превышает целочисленный предел. Я проверил это, используя код вроде: 

unsigned long b, c, c_test;
...
c_test=c*b;         // Possible overflow
if (c_test/b != c) {/* There has been an overflow*/}
else c=c_test;      // No overflow

Есть ли лучший способ проверки на переполнение? Я знаю, что у некоторых чипов есть внутренний флаг, который устанавливается при переполнении, но я никогда не видел, чтобы к нему обращались через C или C ++.

Остерегайтесь того, что переполнение подписано int является неопределенным поведением в C и C ++ , и, следовательно, вы должны обнаружить его, фактически не вызывая его. О переполнении со знаком int перед добавлением см. Обнаружение переполнения со знаком в C / C ++ .

Ответы [ 31 ]

15 голосов
/ 24 июня 2011

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

Идея состоит в том, что именно потому, что процессор просто позволит обернуть значение до нуля, а C / C ++ должен быть абстрагирован от любого конкретного процессора, вы можете: 

uint32_t x, y;
uint32_t value = x + y;
bool overflow = value < (x | y);

Это гарантирует, что если один операнд равен нулю, а другой - нет, переполнение не будет обнаруживаться ложно и будет значительно быстрее, чем множество операций NOT / XOR / AND / test, как предлагалось ранее.

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

uint32_t x, y;
uint32_t value = x + y;
bool overflow = value < x; // Alternatively "value < y" should also work
14 голосов
/ 09 февраля 2009

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

unsigned int r, a, b;
r = a+b;
if (r < a)
{
    // overflow
}

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

signed int r, a, b, s;
r = a+b;
s = a>=0;
if (s == (b>=0) && s != (r>=0))
{
    // overflow
}
13 голосов
/ 14 октября 2008

Вы не можете получить доступ к флагу переполнения из C / C ++.

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

Единственная переносимая и независимая от компилятора вещь, которую вы можете сделать, - это самостоятельно проверить наличие переполнений. Так же, как вы сделали в своем примере.

Edit:

Только что проверил: -ftrapv, кажется, ничего не делает на x86, используя последний GCC. Полагаю, это осталось от старой версии или относится к какой-то другой архитектуре. Я ожидал, что компилятор будет вставлять код операции INTO после каждого добавления. К сожалению, этого не происходит.

11 голосов
/ 21 мая 2012

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

Тест на переполнение со знаком, сложение и вычитание:

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

  2. Вычислить и сравнить знаки операндов.

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

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

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

  3. Проверка на положительное переполнение MAXVALUE.

    а. Если оба знака положительные и MAXVALUE - A б. Если знак B отрицательный и MAXVALUE - A <-B, вычитание будет переполнено. </p>

  4. Проверка на отрицательное переполнение MINVALUE.

    а. Если оба знака отрицательны и MINVALUE - A> B, сложение будет переполнено.

    б. Если знак A отрицательный и MINVALUE - A> B, вычитание будет переполнено.

  5. В противном случае переполнения нет.

Тест на переполнение со знаком, умножение и деление:

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

  2. Вычислите и сравните величины (абсолютные значения) операндов с одним. (Ниже предположим, что А и В - это величины, а не подписанные оригиналы.)

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

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

    с. Если величина одного операнда меньше единицы, а другого больше единицы, умножение не может быть переполнено.

    * * D одна тысяча пятьдесят шесть. Если обе величины меньше единицы, деление не может переполниться.

  3. Проверка на положительное переполнение MAXVALUE.

    а. Если оба операнда больше одного и MAXVALUE / A б. Если B меньше единицы и MAXVALUE * B

  4. В противном случае переполнения нет.

Примечание: минимальное переполнение MINVALUE обрабатывается 3, потому что мы взяли абсолютные значения. Однако если ABS (MINVALUE)> MAXVALUE, тогда у нас будут редкие ложные срабатывания.

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

8 голосов
/ 04 октября 2012

Еще один интересный инструмент: http://embed.cs.utah.edu/ioc/

Это исправленный clang компилятор, который добавляет проверки в код во время компиляции. Таким образом, вы получите вывод, похожий на этот: 

CLANG ARITHMETIC UNDEFINED at <add.c, (9:11)> :
Op: +, Reason : Signed Addition Overflow, 
BINARY OPERATION: left (int32): 2147483647 right (int32): 1
7 голосов
/ 03 октября 2009

CERT разработал новый подход для обнаружения и составления отчетов о целочисленном переполнении со знаком, целочисленном обёртывании без знака и усечении целого числа с использованием целочисленной модели AIR (as-if) с бесконечным ранжированием. CERT опубликовал технический отчет , описывающий модель, и создал рабочий прототип на основе GCC 4.4.0 и GCC 4.5.0.

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

7 голосов
/ 10 января 2014

Другим вариантом решения с использованием ассемблера является внешняя процедура. Этот пример для умножения целых чисел без знака с использованием g ++ и fasm под linux x64.

Эта процедура умножает два целочисленных аргумента без знака (32 бита) (согласно спецификации для amd64 (раздел 3.2.3 Передача параметров)

Если класс INTEGER, используется следующий доступный регистр последовательности% rdi,% rsi,% rdx,% rcx,% r8 и% r9

(регистры edi и esi в моем коде)) и возвращает результат или 0, если произошло переполнение. 

format ELF64

section '.text' executable 

public u_mul

u_mul:
  MOV eax, edi
  mul esi
  jnc u_mul_ret
  xor eax, eax
u_mul_ret:
ret

тест: 

extern "C" unsigned int u_mul(const unsigned int a, const unsigned int b);

int main() {
    printf("%u\n", u_mul(4000000000,2));//0
    printf("%u\n", u_mul(UINT_MAX/2,2));//ok
    return 0;
}

ссылка на программу с объектным файлом asm. В моем случае в Qt Creator добавьте его в LIBS в файле .pro

5 голосов
/ 14 октября 2008

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

5 голосов
/ 05 августа 2013

Попробуйте этот макрос, чтобы проверить бит переполнения 32-битных машин (адаптированный по решению Ангела Синигерского) 

#define overflowflag(isOverflow){   \
size_t eflags;                      \
asm ("pushfl ;"                     \
     "pop %%eax"                    \
    : "=a" (eflags));               \
isOverflow = (eflags >> 11) & 1;}

Я определил его как макрос, потому что в противном случае бит переполнения был бы перезаписан.

Последующее небольшое приложение с кодом сегмента выше: 

#include <cstddef>
#include <stdio.h>
#include <iostream>
#include <conio.h>
#if defined( _MSC_VER )
#include <intrin.h>
#include <oskit/x86>
#endif

using namespace std;

#define detectOverflow(isOverflow){     \
size_t eflags;                      \
asm ("pushfl ;"                     \
    "pop %%eax"                     \
    : "=a" (eflags));               \
isOverflow = (eflags >> 11) & 1;}

int main(int argc, char **argv) {

    bool endTest = false;
    bool isOverflow;

    do {
        cout << "Enter two intergers" << endl;
        int x = 0;
        int y = 0;
        cin.clear();
        cin >> x >> y;
        int z = x * y;
        detectOverflow(isOverflow)
        printf("\nThe result is: %d", z);
        if (!isOverflow) {
            std::cout << ": no overflow occured\n" << std::endl;
        } else {
            std::cout << ": overflow occured\n" << std::endl;
        }

        z = x * x * y;
        detectOverflow(isOverflow)
        printf("\nThe result is: %d", z);
        if (!isOverflow) {
            std::cout << ": no overflow ocurred\n" << std::endl;
        } else {
            std::cout << ": overflow occured\n" << std::endl;
        }

        cout << "Do you want to stop? (Enter \"y\" or \"Y)" << endl;

        char c = 0;

        do {
            c = getchar();
        } while ((c == '\n') && (c != EOF));

        if (c == 'y' || c == 'Y') {
            endTest = true;
        }

        do {
            c = getchar();
        } while ((c != '\n') && (c != EOF));

    } while (!endTest);
}
3 голосов
/ 14 октября 2008

Вы не можете получить доступ к флагу переполнения из C / C ++.

Я не согласен с этим. Вы можете написать некоторый встроенный asm и использовать инструкцию jo (переполнение прыжка), предполагая, что вы находитесь на x86, чтобы перехватить переполнение. Конечно, ваш код больше не будет переносимым на другие архитектуры.

посмотрите на info as и info gcc.

Страница:
...