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

Question

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

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

Однако ложные решения могут быть сгенерированы, когда ^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++".

736

c++ c integer-overflow

Источник

user23732 13 окт '08 в 22:53

31 ответ

Другие вопросы по тегам c++ c integer-overflow

user25324 03 окт '09 в 17:15 2009-10-03 17:15 · Answer 1 · 2009-10-03 17:15

Я вижу, вы используете целые числа без знака. По определению, в C (не знаю о C++) арифметика без знака не переполняется... так что, по крайней мере, для C, ваша точка зрения спорна:)

С целыми числами со знаком, после переполнения, произошло неопределенное поведение, и ваша программа может делать все что угодно (например: сделать тесты неокончательными).

#include <limits.h>
int a = <something>;
int x = <something>;
a += x;              /* UB */
if (a < 0) {         /* unreliable test */
  /* ... */
}

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

// for addition
#include <limits.h>
int a = <something>;
int x = <something>;
if ((x > 0) && (a > INT_MAX - x)) /* `a + x` would overflow */;
if ((x < 0) && (a < INT_MIN - x)) /* `a + x` would underflow */;

// for subtraction
#include <limits.h>
int a = <something>;
int x = <something>;
if ((x < 0) && (a > INT_MAX + x)) /* `a - x` would overflow */;
if ((x > 0) && (a < INT_MIN + x)) /* `a - x` would underflow */;

// for multiplication
#include <limits.h>
int a = <something>;
int x = <something>;
if (a > INT_MAX / x) /* `a * x` would overflow */;
if ((a < INT_MIN / x)) /* `a * x` would underflow */;
// there may be need to check for -1 for two's complement machines
if ((a == -1) && (x == INT_MIN)) /* `a * x` can overflow */
if ((x == -1) && (a == INT_MIN)) /* `a * x` (or `a / x`) can overflow */

для деления (кроме INT_MIN а также -1 особый случай) нет возможности перейти INT_MIN или же INT_MAX,

user251153 06 янв '14 в 18:28 2014-01-06 18:28 · Answer 2 · 2014-01-06 18:28

Clang 3.4+ и GCC 5+ предлагают проверенные арифметические встроенные функции. Они предлагают очень быстрое решение этой проблемы, особенно по сравнению с проверками безопасности при битовом тестировании.

Для примера в вопросе OP, это будет работать так:

unsigned long b, c, c_test;
if (__builtin_umull_overflow(b, c, &c_test))
{
    // returned non-zero: there has been an overflow
}
else
{
    // return zero: there hasn't been an overflow
}

В документации Clang не указано, c_test содержит результат переполнения, если произошло переполнение, но в документации GCC говорится, что это происходит. Учитывая, что эти двое любят быть __builtin-совместимо, вероятно, можно с уверенностью предположить, что именно так работает Clang.

E сть __builtin для каждой арифметической операции, которая может быть переполнена (сложение, вычитание, умножение), с вариантами со знаком и без знака, для размеров int, длинных размеров и длинных длинных размеров. Синтаксис имени __builtin_[us](operation)(l?l?)_overflow:

u для неподписанных или s для подписи;
операция является одним из add, sub или же mul;
нет l суффикс означает, что операнды ints; один l средства long; два lзначит long long,

Так что для проверенного подписанного длинного целого сложения было бы __builtin_saddl_overflow, Полный список можно найти на странице документации Clang.

GCC 5+ и Clang 3.8+ дополнительно предлагают универсальные встроенные функции, которые работают без указания типа значений: __builtin_add_overflow, __builtin_sub_overflow а также __builtin_mul_overflow, Они также работают на типах меньше int,

Встроенные опускаются до того, что лучше для платформы. На x86 они проверяют флаги переноса, переполнения и подписи.

Visual Studio cl.exe не имеет прямых эквивалентов. Для неподписанных дополнений и вычитаний, в том числе <intrin.h> позволит вам использовать addcarry_uNN а также subborrow_uNN (где NN - количество бит, например addcarry_u8 или же subborrow_u64). Их подпись немного тупая:

unsigned char _addcarry_u32(unsigned char c_in, unsigned int src1, unsigned int src2, unsigned int *sum);
unsigned char _subborrow_u32(unsigned char b_in, unsigned int src1, unsigned int src2, unsigned int *diff);

c_in/b_in флаг переноса / заимствования на входе, возвращаемое значение - перенос / заимствование на выходе. Похоже, он не имеет эквивалентов для подписанных операций или умножений.

В противном случае Clang для Windows теперь готов к работе (достаточно для Chrome), так что это тоже может быть вариантом.

user12193 13 окт '08 в 23:44 2008-10-13 23:44 · Answer 3 · 2008-10-13 23:44

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

Кроме того, любые два операнда приведут (не более) на один бит больше, чем старший бит самого большого операнда. Например:

bool addition_is_safe(uint32_t a, uint32_t b) {
    size_t a_bits=highestOneBitPosition(a), b_bits=highestOneBitPosition(b);
    return (a_bits<32 && b_bits<32);
}

Для умножения любые два операнда приведут (не более) к сумме битов операндов. Например:

bool multiplication_is_safe(uint32_t a, uint32_t b) {
    size_t a_bits=highestOneBitPosition(a), b_bits=highestOneBitPosition(b);
    return (a_bits+b_bits<=32);
}

Точно так же вы можете оценить максимальный размер результата a в силу b как это:

bool exponentiation_is_safe(uint32_t a, uint32_t b) {
    size_t a_bits=highestOneBitPosition(a);
    return (a_bits*b<=32);
}

(Конечно, подставьте число бит для целевого целого числа.)

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

size_t highestOneBitPosition(uint32_t a) {
    size_t bits=0;
    while (a!=0) {
        ++bits;
        a>>=1;
    };
    return bits;
}

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

user25222 13 окт '08 в 23:02 2008-10-13 23:02 · Answer 4 · 2008-10-13 23:02

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

Вы также можете проверить возможность переполнения перед выполнением умножения:

if ( b > ULONG_MAX / a ) // a * b would overflow

58

Источник

user25222 13 окт '08 в 23:02

user862391 25 июл '11 в 21:40 2011-07-25 21:40 · Answer 5 · 2011-07-25 21:40

Предупреждение: GCC может оптимизировать проверку переполнения при компиляции с -O2, Опция -Wall в некоторых случаях предупредит вас

if (a + b < a) { /* deal with overflow */ }

но не в этом примере:

b = abs(a);
if (b < 0) { /* deal with overflow */ }

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

Компилирование с -fwrapv решает проблему, но отключает некоторые оптимизации.

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

user942218 28 янв '13 в 17:51 2013-01-28 17:51 · Answer 6 · 2013-01-28 17:51

clang теперь поддерживает динамические проверки переполнения для целых чисел со знаком и без знака. Смотрите -fsanitize= целочисленный ключ. На данный момент это только один компилятор C++ с полностью поддерживаемой динамической проверкой переполнения для целей отладки.

user814674 24 июн '11 в 19:44 2011-06-24 19:44 · Answer 7 · 2011-06-24 19:44

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

Идея состоит в том, что именно потому, что процессор просто позволит обернуть значение до нуля, а 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

user1797000 11 мар '13 в 01:57 2013-03-11 01:57 · Answer 8 · 2013-03-11 01:57

Я вижу, что многие люди ответили на вопрос о переполнении, но я хотел решить его первоначальную проблему. Он сказал, что проблема заключается в том, чтобы найти^b= c таким, чтобы все цифры использовались без повторения. Хорошо, это не то, что он спрашивал в этом посте, но я все еще думаю, что было необходимо изучить верхнюю границу проблемы и сделать вывод, что ему никогда не понадобится рассчитывать или обнаруживать переполнение (примечание: я не опытный в математике, поэтому я сделал это шаг за шагом, но конечный результат был настолько прост, что это может иметь простую формулу).

Суть в том, что верхняя граница, которая требуется для задачи a, b или c, равна 98.765.432. В любом случае, начнем с разбиения задачи на тривиальные и нетривиальные части:

x⁰ == 1 (все перестановки 9, 8, 7, 6, 5, 4, 3, 2 являются решениями)
x¹ == x (решение невозможно)
0^b == 0 (решение невозможно)
1^б == 1 (решение невозможно)
a^b, a> 1, b> 1 (нетривиально)

Теперь нам просто нужно показать, что никакое другое решение невозможно и допустимы только перестановки (и тогда код для их печати тривиален). Возвращаемся к верхней границе. На самом деле верхняя граница составляет c ≤ 98,765,432. Это верхняя граница, потому что это наибольшее число с 8 цифрами (всего 10 цифр минус 1 для каждого a и b). Эта верхняя граница только для c, потому что границы для a и b должны быть намного ниже из-за экспоненциального роста, как мы можем вычислить, варьируя b от 2 до верхней границы:

    9938.08^2 == 98765432
    462.241^3 == 98765432
    99.6899^4 == 98765432
    39.7119^5 == 98765432
    21.4998^6 == 98765432
    13.8703^7 == 98765432
    9.98448^8 == 98765432
    7.73196^9 == 98765432
    6.30174^10 == 98765432
    5.33068^11 == 98765432
    4.63679^12 == 98765432
    4.12069^13 == 98765432
    3.72429^14 == 98765432
    3.41172^15 == 98765432
    3.15982^16 == 98765432
    2.95305^17 == 98765432
    2.78064^18 == 98765432
    2.63493^19 == 98765432
    2.51033^20 == 98765432
    2.40268^21 == 98765432
    2.30883^22 == 98765432
    2.22634^23 == 98765432
    2.15332^24 == 98765432
    2.08826^25 == 98765432
    2.02995^26 == 98765432
    1.97741^27 == 98765432

Обратите внимание, например, на последнюю строку: там написано, что 1.97^27 ~98M. Так, например, 1^27 == 1 и 2^27 == 134.217.728, и это не решение, потому что оно имеет 9 цифр (2 > 1,97, поэтому оно на самом деле больше, чем должно быть проверено). Как видно, комбинации, доступные для тестирования a и b, действительно малы. Для b == 14 нам нужно попробовать 2 и 3. Для b == 3 мы начинаем с 2 и останавливаемся на 462. Все результаты предоставляются как минимум ~ 98M.

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

    ['0', '2', '4', '5', '6', '7', '8'] 84^2 = 7056
    ['1', '2', '3', '4', '5', '8', '9'] 59^2 = 3481
    ['0', '1', '2', '3', '4', '5', '8', '9'] 59^2 = 3481 (+leading zero)
    ['1', '2', '3', '5', '8'] 8^3 = 512
    ['0', '1', '2', '3', '5', '8'] 8^3 = 512 (+leading zero)
    ['1', '2', '4', '6'] 4^2 = 16
    ['0', '1', '2', '4', '6'] 4^2 = 16 (+leading zero)
    ['1', '2', '4', '6'] 2^4 = 16
    ['0', '1', '2', '4', '6'] 2^4 = 16 (+leading zero)
    ['1', '2', '8', '9'] 9^2 = 81
    ['0', '1', '2', '8', '9'] 9^2 = 81 (+leading zero)
    ['1', '3', '4', '8'] 3^4 = 81
    ['0', '1', '3', '4', '8'] 3^4 = 81 (+leading zero)
    ['2', '3', '6', '7', '9'] 3^6 = 729
    ['0', '2', '3', '6', '7', '9'] 3^6 = 729 (+leading zero)
    ['2', '3', '8'] 2^3 = 8
    ['0', '2', '3', '8'] 2^3 = 8 (+leading zero)
    ['2', '3', '9'] 3^2 = 9
    ['0', '2', '3', '9'] 3^2 = 9 (+leading zero)
    ['2', '4', '6', '8'] 8^2 = 64
    ['0', '2', '4', '6', '8'] 8^2 = 64 (+leading zero)
    ['2', '4', '7', '9'] 7^2 = 49
    ['0', '2', '4', '7', '9'] 7^2 = 49 (+leading zero)

Ни один из них не соответствует проблеме (что также видно по отсутствию '0', '1', ..., '9').

Пример кода, который решает это следующим образом. Также обратите внимание, что он написан на python не потому, что ему нужны произвольные целые числа точности (код не рассчитывает ничего больше, чем 98 миллионов), а потому, что мы обнаружили, что количество тестов настолько мало, что мы должны использовать язык высокого уровня для использовать его встроенные контейнеры и библиотеки (также обратите внимание: код имеет 28 строк).

    import math

    m = 98765432
    l = []
    for i in xrange(2, 98765432):
        inv = 1.0/i
        r = m**inv
        if (r < 2.0): break
        top = int(math.floor(r))
        assert(top <= m)

        for j in xrange(2, top+1):
            s = str(i) + str(j) + str(j**i)
            l.append((sorted(s), i, j, j**i))
            assert(j**i <= m)

    l.sort()
    for s, i, j, ji in l:
        assert(ji <= m)
        ss = sorted(set(s))
        if s == ss:
            print '%s %d^%d = %d' % (s, i, j, ji)

        # Try with non significant zero somewhere
        s = ['0'] + s
        ss = sorted(set(s))
        if s == ss:
            print '%s %d^%d = %d (+leading zero)' % (s, i, j, ji)

user754396 07 дек '12 в 13:48 2012-12-07 13:48 · Answer 9 · 2012-12-07 13:48

Вот "непереносимое" решение вопроса. Процессоры Intel x86 и x64 имеют так называемый EFLAGS-регистр ( http://en.wikipedia.org/wiki/EFLAGS), который заполняется процессором после каждой целочисленной арифметической операции. Я пропущу подробное описание здесь. Соответствующими флагами являются флаг "Переполнение" (маска 0x800) и флаг "Перенос" (маска 0x1). Чтобы правильно их интерпретировать, следует учитывать, имеют ли операнды тип со знаком или без знака.

Вот практический способ проверить флаги из C/C++. Следующий код будет работать в Visual Studio 2005 или более поздней версии (как 32-разрядной, так и 64-разрядной), а также в 64-разрядной версии GNU C/C++.

#include <cstddef>
#if defined( _MSC_VER )
#include <intrin.h>
#endif

inline size_t query_intel_x86_eflags( const size_t query_bit_mask )
{
#if defined( _MSC_VER )
    return __readeflags() & query_bit_mask;
#elif defined( __GNUC__ )
    // this code will work only on 64-bit GNU-C machines;
    // Tested and does NOT work with Intel C++ 10.1!
    size_t eflags;
    __asm__ __volatile__(
        "pushfq \n\t"
        "pop %%rax\n\t"
        "movq %%rax, %0\n\t"
        :"=r"(eflags)
        :
        :"%rax"
        );
    return eflags & query_bit_mask;
#else
#pragma message("No inline assembly will work with this compiler!")
    return 0;
#endif
}

int main(int argc, char **argv)
{
    int x = 1000000000;
    int y = 20000;
    int z = x * y;
    int f = query_intel_x86_eflags( 0x801 );
    printf( "%X\n", f );
}

Если бы операнды были умножены без переполнения, вы получите возвращаемое значение 0 из query_intel_eflags( 0x801), т.е. не установлены ни флаги переноса, ни флаги переполнения. В приведенном примере кода main() происходит переполнение, и оба флага установлены в 1. Эта проверка не подразумевает каких-либо дальнейших вычислений, поэтому она должна быть достаточно быстрой.

user13430 14 окт '08 в 01:05 2008-10-14 01:05 · Answer 10 · 2008-10-14 01:05

Если у вас есть тип данных, который больше, чем тот, который вы хотите проверить (скажем, вы делаете 32-битное добавление и у вас есть 64-битный тип). Затем он обнаружит переполнение. Мой пример для 8-битного добавления. Но можно увеличить.

uint8_t x, y;   /* give these values */
const uint16_t data16   = x + y;
const bool carry        = (data16 > 0xff);
const bool overflow     = ((~(x ^ y)) & (x ^ data16) & 0x80);

Он основан на концепциях, описанных на этой странице: http://www.cs.umd.edu/class/spring2003/cmsc311/Notes/Comb/overflow.html

Для 32-битного примера 0xff становится 0xffffffff а также 0x80 становится 0x80000000 и наконец uint16_t становится uint64_t,

ПРИМЕЧАНИЕ: это ловит целочисленные переполнения сложения / вычитания, и я понял, что ваш вопрос связан с умножением. В этом случае, разделение, вероятно, лучший подход. Обычно это способ calloc реализации гарантируют, что параметры не переполняются, поскольку они умножены, чтобы получить окончательный размер.

user11694 13 окт '08 в 22:59 2008-10-13 22:59 · Answer 11 · 2008-10-13 22:59

Самый простой способ - конвертировать ваши unsigned longс в unsigned long longs, сделайте свое умножение и сравните результат с 0x100000000LL.

Вы, вероятно, обнаружите, что это более эффективно, чем деление, как вы делали в своем примере.

О, и это будет работать как на C, так и на C++ (как вы пометили вопрос обоими).

Просто взглянул на руководство по glibc. Есть упоминание о целочисленном переполнении (FPE_INTOVF_TRAP) как часть SIGFPE, Это было бы идеально, если не считать неприятных моментов в руководстве:

FPE_INTOVF_TRAP Целочисленное переполнение (невозможно в программе на C, если вы не включаете перехват переполнения аппаратным способом).

Немного стыдно на самом деле.

user15955 13 окт '08 в 22:59 2008-10-13 22:59 · Answer 12 · 2008-10-13 22:59

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

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

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

Редактировать:

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

09 фев '09 в 14:06 2009-02-09 14:06 · Answer 13 · 2009-02-09 14:06

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

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
}

user127251 21 май '12 в 14:53 2012-05-21 14:53 · Answer 14 · 2012-05-21 14:53

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

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

Получите константы, которые представляют наибольшее и наименьшее возможные значения для типа, MAXVALUE и MINVALUE.
Вычислить и сравнить знаки операндов.
а. Если любое значение равно нулю, то ни сложение, ни вычитание не могут переполниться. Пропустить оставшиеся тесты.
б. Если знаки противоположны, то сложение не может переполниться. Пропустить оставшиеся тесты.
с. Если знаки совпадают, вычитание не может быть переполнено. Пропустить оставшиеся тесты.
Тест на положительное переполнение MAXVALUE.
а. Если оба знака положительные и MAXVALUE - A
б. Если знак B отрицательный и MAXVALUE - A <-B, вычитание будет переполнено.
Проверка на отрицательное переполнение MINVALUE.
а. Если оба знака отрицательны и MINVALUE - A > B, сложение будет переполнено.
б. Если знак A отрицательный и MINVALUE - A > B, вычитание будет переполнено.
В противном случае, нет переполнения.

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

Получите константы, которые представляют наибольшее и наименьшее возможные значения для типа, MAXVALUE и MINVALUE.
Вычислить и сравнить величины (абсолютные значения) операндов с одним. (Ниже предположим, что А и В - это величины, а не подписанные оригиналы.)
а. Если любое из значений равно нулю, умножение не может переполниться, и деление даст ноль или бесконечность.
б. Если любое из значений равно единице, умножение и деление не могут переполниться.
с. Если величина одного операнда меньше одного, а другого больше единицы, умножение не может быть переполнено.
д. Если обе величины меньше единицы, деление не может переполниться.
Тест на положительное переполнение MAXVALUE.
а. Если оба операнда больше одного и MAXVALUE / A
б. Если B меньше единицы и MAXVALUE * B
В противном случае, нет переполнения.

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

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

user1049677 04 окт '12 в 12:08 2012-10-04 12:08 · Answer 15 · 2012-10-04 12:08

Еще один интересный инструмент: 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

10

Источник

user1049677 04 окт '12 в 12:08

user183661 03 окт '09 в 16:46 2009-10-03 16:46 · Answer 16 · 2009-10-03 16:46

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

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

user704244 10 янв '14 в 17:15 2014-01-10 17:15 · Answer 17 · 2014-01-10 17:15

Другой вариант решения с использованием ассемблера - это внешняя процедура. Этот пример для целочисленного умножения без знака с использованием 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

user2653743 05 авг '13 в 15:47 2013-08-05 15:47 · Answer 18 · 2013-08-05 15:47

Попробуйте этот макрос, чтобы проверить бит переполнения 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);
}

user15416 14 окт '08 в 07:30 2008-10-14 07:30 · Answer 19 · 2008-10-14 07:30

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

user27653 13 окт '08 в 23:25 2008-10-13 23:25 · Answer 20 · 2008-10-13 23:25

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

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

посмотри на info as а также info gcc,

user18721 15 мар '18 в 15:55 2018-03-15 15:55 · Answer 21 · 2018-03-15 15:55

mozilla::CheckedInt<T> обеспечивает целочисленную математику с проверкой переполнения для целочисленного типа T (используя встроенные функции компилятора в clang и gcc, если доступно). Код под MPL 2.0 и зависит от трех (IntegerTypeTraits.h, Attributes.h а также Compiler.h) другие нестандартные заголовки библиотек, содержащие только заголовки, плюс механизм подтверждения для Mozilla. Возможно, вы захотите заменить механизм подтверждения, если импортируете код.

user53974 01 май '10 в 18:36 2010-05-01 18:36 · Answer 22 · 2010-05-01 18:36

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

2

Источник

user53974 01 май '10 в 18:36

user3945377 18 ноя '15 в 19:29 2015-11-18 19:29 · Answer 23 · 2015-11-18 19:29

Набор команд x86 включает в себя инструкцию умножения без знака, которая сохраняет результат в двух регистрах. Чтобы использовать эту инструкцию из C, можно написать следующий код в 64-битной программе (gcc):

unsigned long checked_imul(unsigned long a, unsigned long b) {
  __int128 res = (__int128)a * (__int128)b;
  if ((unsigned long)(res >> 64))
    printf("overflow in integer multiply");
  return (unsigned long)res;
}

Для 32-битной программы результат должен быть 64-битным, а параметры - 32-битными.

Альтернативой является использование зависимых от компилятора инстинктов для проверки регистра флага. Документацию GCC для инстинктов переполнения можно найти по https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins.html

user1069178 13 фев '13 в 17:34 2013-02-13 17:34 · Answer 24 · 2013-02-13 17:34

Чтобы расширить ответ Head Geek, есть более быстрый способ сделать addition_is_safe;

bool addition_is_safe(unsigned int a, unsigned int b)
{
    unsigned int L_Mask = std::numeric_limits<unsigned int>::max();
    L_Mask >>= 1;
    L_Mask = ~L_Mask;

    a &= L_Mask;
    b &= L_Mask;

    return ( a == 0 || b == 0 );
}

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

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

user8964 14 окт '08 в 18:43 2008-10-14 18:43 · Answer 25 · 2008-10-14 18:43

@MSalters: хорошая идея.

Если требуется целочисленное вычисление (для точности), но имеется плавающая точка, вы можете сделать что-то вроде:

uint64_t foo( uint64_t a, uint64_t b ) {
    double   dc;

    dc = pow( a, b );

    if ( dc < UINT_MAX ) {
       return ( powu64( a, b ) );
    }
    else {
      // overflow
    }
}

-1

Источник

user8964 14 окт '08 в 18:43

user3153 13 окт '08 в 23:07 2008-10-13 23:07 · Answer 26 · 2008-10-13 23:07

Чистым способом сделать это было бы переопределение всех операторов (в частности, + и *) и проверка на переполнение перед выполнением операций.

-1

Источник

user3153 13 окт '08 в 23:07

user2352564 20 июн '14 в 19:22 2014-06-20 19:22 · Answer 27 · 2014-06-20 19:22

#include <stdio.h>
#include <stdlib.h>

#define MAX 100 

int mltovf(int a, int b)
{
    if (a && b) return abs(a) > MAX/abs(b);
    else return 0;
}

main()
{
    int a, b;

    for (a = 0; a <= MAX; a++)
        for (b = 0; b < MAX; b++) {

        if (mltovf(a, b) != (a*b > MAX)) 
            printf("Bad calculation: a: %d b: %d\n", a, b);

    }
}

-2

Источник

user2352564 20 июн '14 в 19:22

user2844725 03 окт '13 в 23:43 2013-10-03 23:43 · Answer 28 · 2013-10-03 23:43

Это зависит от того, для чего вы его используете. Для выполнения сложения без знака (DWORD) или умножения лучшим решением будет использование ULARGE_INTEGER.

ULARGE_INTEGER - это структура двух DWORD. Полное значение может быть доступно как "QuadPart", в то время как hi DWORD - как "HighPart", а низкий DWORD - как "LowPart".

Например:

DWORD My Addition (DWORD Value_A, DWORD Value_B) {ULARGE_INTEGER a, b;

   b.LowPart = Value_A;  // a 32 bit value(up to 32 bit)
   b.HighPart = 0;
   a.LowPart = Value_B;  // a 32 bit value(up to 32 bit)
   a.HighPart = 0;

   a.QuadPart += b.QuadPart;

   // if  a.HighPart
   // Then a.HighPart contains the overflow(carry)

   return (a.LowPart + a.HighPart)

// любое переполнение сохраняется в a.HighPart(до 32 бит)

user1655700 21 янв '15 в 21:28 2015-01-21 21:28 · Answer 29 · 2015-01-21 21:28

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

... /* begin multiplication */
unsigned multiplicand, multiplier, product, productHalf;
int zeroesMultiplicand, zeroesMultiplier;
zeroesMultiplicand = number_of_leading_zeroes( multiplicand );
zeroesMultiplier   = number_of_leading_zeroes( multiplier );
if( zeroesMultiplicand + zeroesMultiplier <= 30 ) goto overflow;
productHalf = multiplicand * ( c >> 1 );
if( (int)productHalf < 0 ) goto overflow;
product = productHalf * 2;
if( multiplier & 1 ){
   product += multiplicand;
   if( product < multiplicand ) goto overflow;
}
..../* continue code here where "product" is the correct product */
....
overflow: /* put overflow handling code here */

int number_of_leading_zeroes( unsigned value ){
   int ctZeroes;
   if( value == 0 ) return 32;
   ctZeroes = 1;
   if( ( value >> 16 ) == 0 ){ ctZeroes += 16; value = value << 16; }
   if( ( value >> 24 ) == 0 ){ ctZeroes +=  8; value = value <<  8; }
   if( ( value >> 28 ) == 0 ){ ctZeroes +=  4; value = value <<  4; }
   if( ( value >> 30 ) == 0 ){ ctZeroes +=  2; value = value <<  2; }
   ctZeroes -= x >> 31;
   return ctZeroes;
}

user5274 13 окт '08 в 22:59 2008-10-13 22:59 · Answer 30 · 2008-10-13 22:59

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

-3

Источник

user5274 13 окт '08 в 22:59