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

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

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

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

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


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

Ответы [ 31 ]

194 голосов
/ 03 октября 2009

Я вижу, вы используете целые числа без знака. По определению, в 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'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.

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

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

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

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

131 голосов
/ 06 января 2014

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, длинных размеров и длинных длинных размеров. Синтаксис имени: __builtin_[us](operation)(l?l?)_overflow:

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

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

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

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

if ( b > ULONG_MAX / a ) // a * b would overflow
38 голосов
/ 26 июля 2011

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

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

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

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

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

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

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

30 голосов
/ 28 января 2013

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

23 голосов
/ 07 декабря 2012

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

23 голосов
/ 11 марта 2013

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

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

  • x 0 == 1 (все перестановки 9, 8, 7, 6, 5, 4, 3, 2 являются решениями)
  • x 1 == 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)
20 голосов
/ 14 октября 2008

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

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

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

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

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


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

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

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

...