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

Ответ 1

Я вижу, вы используете целые числа без знака. По определению, в 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>;
// there may be need to check for -1 for two 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.

Ответ 2

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

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

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

Ответ 3

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 -compatible, вероятно, можно с уверенностью предположить, что так работает Clang.

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

• u для unsigned или s для подписания;
• операция является одним из add, sub или mul;
• no l suffix означает, что операнды являются int s; один 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), так что это тоже вариант.

Ответ 4

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

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

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

Ответ 5

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

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

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

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

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

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

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

Ответ 6

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

Ответ 7

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

Вот практический способ проверить флаги на C/С++. Следующий код будет работать на Visual Studio 2005 или новее (как на 32, так и на 64 бит), а также на 64-битном языке GNU 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. Эта проверка не подразумевает дальнейших вычислений, поэтому она должна быть довольно быстрой.

Ответ 8

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

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

• x ⁰ == 1 (все перестановки 9, 8, 7, 6, 5, 4, 3, 2 являются решениями)
• x ¹ == x (невозможно решение)
• 0 ^b == 0 (невозможно решение)
• 1 ^b == 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)

Ответ 9

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

Ответ 10

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

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

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

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

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

Немного постыдно.

Ответ 11

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

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

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

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

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

uint32_t x, y;
uint32_t value = x + y;
bool overflow = value < x; // Alternatively "value < y" should also work

Ответ 12

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

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

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

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

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

Edit:

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

Ответ 14

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

Подписанный тест переполнения, добавление и вычитание:

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

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

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

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

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

• Проверьте положительное переполнение MAXVALUE.

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

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

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

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

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

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

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

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

• Вычислить и сравнить величины (абсолютные значения) операндов с единицей. (Ниже предполагается, что A и B - эти величины, а не подписанные оригиналы.)

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

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

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

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

• Проверьте положительное переполнение MAXVALUE.

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

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

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

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

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

Ответ 15

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

Ответ 16

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

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

Ответ 17

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

Ответ 18

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

Ответ 19

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

Ответ 20

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

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

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

Ответ 21

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

Ответ 22

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

Ответ 23

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

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

Ответ 24

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

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

Ответ 25

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

Ответ 26

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

template<typename Int>
 bool overflows(Int lhs, Int rhs)
 {
     return (lhs + rhs) < lhs;
 }



 shrl $31, %esi
 movl %esi, %eax
 retq

Это своего рода дрожь, потому что это действительно плохо. Это на самом деле ничего не делает, верно? На самом деле это не проверка того, что вы хотите. То, что он делает, просто сдвиг вправо, а затем, как будто просто вернул верхний бит, чтобы увидеть, было ли это отрицательно или нет. Поэтому он не проверяет переполнение. Это ничего не добавляет. Вы сказали, чтобы добавить его в add, потому что подписанное переполнение не определено. Компилятор идет и хорошо говорит, что не может переполняться, и поэтому я просто проверю, был ли он отрицательным или что-то еще. Одно замечание: здесь приведен пример кода, который проверяет только положительное переполнение. Поэтому он не проверяет отрицательное переполнение. Итак, предположим, что вход положительный. Поэтому он не проверяет отрицательное переполнение. Так что просто ищите переполнение выше int max.

template<typename Int>
bool overflows(Int lhs, Int rhs)
{
    using U = std::make_unsigned_t<Int>;
    return (U(lhs) + U(rhs)) < lhs;
}

addl %edi, %esi
setb %al
ret

Здесь мы получаем addl а затем setb который устанавливает флаг и возвращает регистр (al). Так что этот код правильный. Он правильно проверяет положительное переполнение. И причина, по которой это правильно, заключается в том, что в C++ неподписанное переполнение корректно определено, но переполнение подписей - нет. Итак, что вы делаете, вы буквально говорите, что переводите это число без знака, а затем делаете добавление, а затем просто проверяете, теперь он отрицательный или нет, сумма меньше, чем левая сторона или нет. И действительно, это код, который вы хотите получить, но это не интуитивно понятный код. Если вы дадите этот код большинству людей, они такие, как будто это сбивает с толку. Это не очевидно, что вы должны это написать.

template<typename Int>
bool overflows(Int lhs, Int rhs)
{
    auto max = std::nummeric_limits<decltype(lhs) > ::max();
    return lhs > max - rhs;
}

movl $2147483647, %eax
subl %esi, %eax
cmpl %edi, %eax
setl %al
ret

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

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

template<typename Int>
bool overflows(Int lhr, Int rhs)
{
    _Atomic Int = lhs;
    return ((a += rhs), a) < lhs;
}

movl %edi, -4(%rsp)
lock addl %esi, -4(%rsp)
movl -4(%rsp), %eax
cmpl %edi, %eax
setl %al
ret

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

template<typename Int>
bool overflows(Int lhs, Int rhs)
{
    struct S { S(int a) : a(a); long long a:32;} s(lhs);
    return ((s.a += rhs), s.a) < lhs;
}

shrl $31, %esi
movl %esi, %eax
retq

Умные люди выйдут и скажут, что на самом деле битовые поля являются особенными. Теперь особенно важны битовые поля, когда левый операнд оператора присваивания является битовым полем, которое не может представлять значение выражения, результирующее значение битового поля определяется реализацией. Скомпилируйте его с помощью clang, boom. Это не работает (как и в первом случае выше). GCC, MSVC, ICC генерируют правильный (сборный) код. Вы проверяете это на GCC, поступаете правильно. Хорошо, отправляй его. Перекомпилируйте его в Clang, он больше не работает. Это ужасно.

template<typename Int>
bool overflows(Int lhs, Int rhs)
{
    auto min = std::numeric_limits<Int>::min();
    auto max = std::numeric_limits<Int>::max();
    return (rhs < 0) ? (lhs < min - rhs) : (lhs > max - rhs);
}

testl %esi, %esi
jm .LBB0_1
movl $2147483647, %eax
subl %esi, %eax
cmpl %edi, %eax
setl %al
retq
.LBB0_1:
movslq %edi, %rax
movq $-2147483648, %rdx
subq %rcx, %rdx
cmpq %rax, %rdx
setq %al
retq

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

template<typename Int>
bool overflows(Int lhs, Int rhs)
{
    Int tmp;
    return __builtin_add_overflow(lhs, rhs, &tmp);
}

addl %esi, %edi
seto %al
retq

Обратитесь за помощью к компилятору. Итак, вот что в компиляторе называется builtins. Вы можете добавить добавление с переполнением. Что это значит, в этом случае вы помещаете значение типа, который вы пытаетесь добавить, вы передаете его в качестве ссылки, а затем он поместит результат там, и он вернет вам bool говоря, есть ли у вас переполнение или нет. И что здорово с этим во встроенном, это будет определять как положительное переполнение, так и отрицательное переполнение. И код, который вы выходите из него, довольно милый. Итак, что он здесь делает, в этом случае используется флаги CPU вместо того, чтобы просто проверять как положительное переполнение, проверьте оба. И это имеет место в случае X86, команда seto была просто установлена, если установлен бит переполнения. Итак, одно, что нужно понять о процессорах, - это когда вы делаете такие вещи, как добавление, умножение и другие подобные вещи, они будут обновлять внутренние флаги. Таким образом, флаг переноса, флаг переполнения, выглядит так. Все процессоры имеют разные флаги, но они вроде морально делают то же самое. Они просто отслеживают состояние некоторых вещей. Потому что делать добавление - это просто куча проводов, которые делают что-то, а затем один провод, который выходит, и что флаг переноса или что-то в этом роде. Поэтому, если вы посмотрите на свое руководство по компиляции или руководство по процессору, оно объяснит, какие флаги у вас есть. Теперь, к счастью, компиляторы делают это за вас. Так что это идеальный код для того, что мы пытаемся сделать. Я просто хочу знать, случится ли переполнение. И эта инструкция seto делает именно это. Поэтому помните, что у C++ есть неопределенное поведение, когда вы добавляете целочисленное целое, ваше оборудование не работает. И поэтому источником многих разочарований я пытаюсь проверить переполнение по соображениям безопасности или что-то еще, и я знаю, что мое оборудование может сделать это действительно, действительно дешево.

Ответ 27

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

Ответ 28

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

    }
}

Ответ 29

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

Ответ 30

Простым способом проверки переполнения является проверка правильности, проверяя, меньше ли текущее значение, чем предыдущее значение. Например, предположим, что у вас был цикл для печати степеней 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;
}

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

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