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

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

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

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

#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>;
// There may be a need to check for -1 for two's complement machines.
// If one number is -1 and another is INT_MIN, multiplying them we get abs(INT_MIN) which is 1 higher than INT_MAX
if ((a == -1) && (x == INT_MIN)) /* `a * x` can overflow */
if ((x == -1) && (a == INT_MIN)) /* `a * x` (or `a / x`) can overflow */
// general case
if (a > INT_MAX / x) /* `a * x` would overflow */;
if ((a < INT_MIN / x)) /* `a * x` would underflow */;

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

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

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

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функции, но это может произойти (особенно если вы знали, сколько битов было в операндах заранее).

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.

Для __builtinкаждой арифметической операции существует возможность переполнения (сложение, вычитание, умножение) с вариантами со знаком и без знака, для размеров int, long и long long. Синтаксис имени __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 они проверяют флаги переноса, переполнения и подписи.

Файл cl.exe в Visual Studio не имеет прямых эквивалентов. Для беззнаковых сложений и вычитаний, включая <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), так что это тоже может быть вариантом.

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

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

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

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

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

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

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

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

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

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

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

Я вижу, что многие люди ответили на вопрос о переполнении, но я хотел решить его первоначальную проблему. Он сказал, что проблема в том, чтобы найти ^б = 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)

Вот «непереносимое» решение вопроса. Процессоры Intel x86 и x64 имеют так называемый 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. Эта проверка не подразумевает каких-либо дальнейших вычислений, поэтому она должна быть достаточно быстрой.

Если у вас есть тип данных, который больше, чем тот, который вы хотите протестировать (скажем, вы делаете 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реализации гарантируют, что параметры не переполняются, поскольку они умножены, чтобы получить окончательный размер.

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

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

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

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

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

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

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

Идея состоит в том, что именно потому, что процессор просто позволит обернуть значение до нуля, а 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;
const bool overflow = value < x; // Alternatively "value < y" should also work

Более эффективный и дешевый способ обнаружения переполнения умножения:

uint32_t x, y;
const bool overflow = (x >> 16U) * (y >> 16U);
uint32_t value = overflow ? UINT32_MAX : x * y;

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

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

Некоторые компиляторы позволяют вставлять в код инструкции ловушки. На GCC вариант есть -ftrapv.

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

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

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

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
}

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

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

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

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

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

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

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

3. Тест на положительное переполнение MAXVALUE.

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

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

4. Тест на отрицательное переполнение MINVALUE.

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

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

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

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

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

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

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

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

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

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

3. Тест на положительное переполнение MAXVALUE.

   а. Если оба операнда больше одного и MAXVALUE / A <B, умножение будет переполнено.

   б. Если B меньше единицы и MAXVALUE * B <A, деление будет переполнено.

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

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

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

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

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

Еще одним интересным инструментом является IOC: средство проверки переполнения целых чисел для C / C ++ .

Это исправленный компилятор Clang , который добавляет проверки в код во время компиляции.

Вы получите вывод, похожий на этот:

CLANG ARITHMETIC UNDEFINED at <add.c, (9:11)> :
Op: +, Reason : Signed Addition Overflow,
BINARY OPERATION: left (int32): 2147483647 right (int32): 1

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

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

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

#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);
}

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

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

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

Посмотрите info asи info gcc.

Чтобы расширить ответ 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-разрядные целые числа без знака будут работать нормально. По сути, я создаю маску, которая будет маскировать все, кроме самого значимого бита. Затем я маскирую оба целых числа, и если ни у одного из них не установлен этот бит, то сложение безопасно.

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

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

Ответ MSalter - хорошая идея.

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

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
    }
}

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

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

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

Альтернативой является использование зависимой от компилятора встроенной функции для проверки регистра флага. Документацию GCC для встроенного переполнения можно найти в 6.56 «Встроенные функции для выполнения арифметики с проверкой переполнения» .

#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);

    }
}

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

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

ULARGE_INTEGER - это структура двух DWORD. Полное значение может быть доступно как «QuadPart», в то время как высокий 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)

    // Any overflow is stored in a.HighPart (up to 32 bits)

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

... /* 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;
}

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

long lng;
int n;
for (n = 0; n < 34; ++n)
{
   lng = pow (2, n);
   printf ("%li\n", lng);
}

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

long signed lng, lng_prev = 0;
int n;
for (n = 0; n < 34; ++n)
{
    lng = pow (2, n);
    if (lng <= lng_prev)
    {
        printf ("Overflow: %i\n", n);
        /* Do whatever you do in the event of overflow.  */
    }
    printf ("%li\n", lng);
    lng_prev = lng;
}

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

Конечно, если вы хотите сделать что-то похожее для уменьшения значений вместо увеличения значений, вы бы изменили <=знак, чтобы сделать это >=, предполагая, что поведение недостаточного значения совпадает с поведением переполнения. Честно говоря, он настолько переносим, ​​насколько вы получите без доступа к флагу переполнения ЦП (и для этого потребуется встроенный код сборки, что делает ваш код непереносимым между реализациями в любом случае).