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

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

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

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

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

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

FPE_INTOVF_TRAP Integer overflow (impossible in a C program unless you enable overflow trapping in a hardware-specific fashion).

На самом деле немного обидно.

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

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

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

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

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

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

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

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

You can't access the overflow flag from C/C++.

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

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

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

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

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

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

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

Ответ 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
    }
}

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

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
}

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

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

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

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

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

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

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

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

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

Идея состоит в том, что именно потому, что процессор просто позволяет значению вернуться к нулю и что 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 uint32_t a = (x >> 16U) * (y & 0xFFFFU);
const uint32_t b = (x & 0xFFFFU) * (y >> 16U);
const bool overflow = ((x >> 16U) * (y >> 16U)) +
    (a >> 16U) + (b >> 16U);
uint32_t value = overflow ? UINT32_MAX : x * y;

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

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

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

uint32_t x, y;
const bool overflow
{
    [](const uint32_t x, const uint32_t y) noexcept -> bool
    {
        const uint32_t a{(x >> 16U) * uint16_t(y)};
        const uint32_t b{uint16_t(x) * (y >> 16U)};
        return ((x >> 16U) * (y >> 16U)) + (a >> 16U) + (b >> 16U);
    }(x, y)
};
uint32_t value{overflow ? UINT32_MAX : x * y};

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Подписанный тест переполнения, умножение и деление:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Вы получите следующий результат:

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

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

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

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

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

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

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

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

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 означает, что это операнды 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 они проверяют флаги переноса, переполнения и подписи.

Файл 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), так что это тоже может быть вариантом.

Другой вариант решения, использующий язык ассемблера, - это внешняя процедура. Этот пример для беззнакового целочисленного умножения с использованием g ++ и fasm в Linux x64.

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

If the class is INTEGER, the next available register of the sequence %rdi, %rsi, %rdx, %rcx, %r8, and %r9 is used

(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.

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

    }
}

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

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

Набор инструкций 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 Встроенные функции для выполнения арифметических операций с проверкой переполнения.

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