Каков лучший способ c++ умножать целые числа без знака по модулю безопасно?

Предположим, что вы используете <cstdint> и типы, такие как std::uint8_t и std::uint16_t, и хотите выполнять над ними операции, такие как += и *=. Вы хотели бы, чтобы арифметика на этих числах обертывалась по модулю, как обычно в C / C++. Это обычно работает, и вы находите экспериментально работает с std::uint8_t, std::uint32_t и std::uint64_t, но не std::uint16_t.

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

std::uint16_t x = UINT16_C(0xFFFF);
x *= x;
Причина заключается в правилах продвижения C++и в том, что вы, как и почти все в наши дни, используете платформу, на которой std::numeric_limits<int>::digits == 31. То есть int является 32-разрядным (digits считает биты, но не знаковый бит). x получает повышение до signed int, несмотря на отсутствие знака, и 0xFFFF * 0xFFFF переполнения для 32-разрядной знаковой арифметики.

Демонстрация общей задачи: 

// Compile on a recent version of clang and run it:
// clang++ -std=c++11 -O3 -Wall -fsanitize=undefined stdint16.cpp -o stdint16

#include <cinttypes>
#include <cstdint>
#include <cstdio>

int main()
{
     std::uint8_t a =  UINT8_MAX; a *= a; // OK
    std::uint16_t b = UINT16_MAX; b *= b; // undefined!
    std::uint32_t c = UINT32_MAX; c *= c; // OK
    std::uint64_t d = UINT64_MAX; d *= d; // OK

    std::printf("%02" PRIX8 " %04" PRIX16 " %08" PRIX32 " %016" PRIX64 "n",
        a, b, c, d);

    return 0;
}

Вы получите хорошую ошибку: 

main.cpp:11:55: runtime error: signed integer overflow: 65535 * 65535
    cannot be represented in type 'int'
Способ избежать этого, конечно, состоит в том, чтобы бросить по крайней мере unsigned int перед умножением. Только точный случай, когда число битов беззнакового типа точно равно половине числа битов int, является проблематичным. Любое меньшее значение приведет к тому, что умножение не сможет переполниться, как в случае std::uint8_t; любой больший размер приведет к тому, что тип точно соответствует одному из рангов продвижения, как с std::uint64_t соответствием unsigned long или unsigned long long в зависимости от платформы.

Но это действительно отстой: требуется знать, какой тип проблематичен, основываясь на размере int на текущей платформе. Есть ли какой-то лучший способ, с помощью которого неопределенное поведение с беззнаковым целочисленным умножением можно избежать без #if лабиринтов?

3 28
c++ portability undefined-behavior

3 ответа:

Возможно, какое-то шаблонное метапрограммирование с помощью SFINAE.

#include <type_traits>

template <typename T, typename std::enable_if<std::is_unsigned<T>::value && (sizeof(T) <= sizeof(unsigned int)) , int>::type = 0>
T safe_multiply(T a, T b) {
    return (unsigned int)a * (unsigned int)b;
}

template <typename T, typename std::enable_if<std::is_unsigned<T>::value && (sizeof(T) > sizeof(unsigned int)) , int>::type = 0>
T safe_multiply(T a, T b) {
    return a * b;
}

Демо .

Edit : проще: 

template <typename T, typename std::enable_if<std::is_unsigned<T>::value, int>::type = 0>
T safe_multiply(T a, T b) {
    typedef typename std::make_unsigned<decltype(+a)>::type typ;
    return (typ)a * (typ)b;
}

Демо .

9

Вот относительно простое решение, которое заставляет продвижение к unsigned int вместо int для беззнакового типа уже, чем int. Я не думаю, что какой-либо код генерируется promote, или, по крайней мере, не больше кода, чем стандартное целочисленное продвижение; это просто заставит умножение и т. д. чтобы использовать неподписанные операции вместо подписанных: 

#include <type_traits>
// Promote to unsigned if standard arithmetic promotion loses unsignedness
template<typename integer> 
using promoted =
  typename std::conditional<std::numeric_limits<decltype(integer() + 0)>::is_signed,
                            unsigned,
                            integer>::type;

// function for template deduction
template<typename integer>
constexpr promoted<integer> promote(integer x) { return x; }

// Quick test
#include <cstdint>
#include <iostream>
#include <limits>
int main() {
  uint8_t i8 = std::numeric_limits<uint8_t>::max(); 
  uint16_t i16 = std::numeric_limits<uint16_t>::max(); 
  uint32_t i32 = std::numeric_limits<uint32_t>::max(); 
  uint64_t i64 = std::numeric_limits<uint64_t>::max();
  i8 *= promote(i8);
  i16 *= promote(i16);
  i32 *= promote(i32);
  i64 *= promote(i64);

  std::cout << " 8: " << static_cast<int>(i8) << std::endl
            << "16: " << i16 << std::endl
            << "32: " << i32 << std::endl
            << "64: " << i64 << std::endl;
  return 0;
}
7

Эта статья, касающаяся решения C для случая uint32_t * uint32_t умножения на систему, в которой int является 64 битами, имеет действительно простое решение, о котором я не думал: 32-битное беззнаковое умножение на 64 бит, вызывающее неопределенное поведение?

Это решение, в переводе на мою задачу, просто: 

static_cast<std::uint16_t>(1U * x * x)

Простое включение 1U в левую часть цепочки таких арифметических операций повысит первый параметр до большего ранга unsigned int и std::uint16_t, а затем так далее вниз по цепочке. Повышение гарантирует, что ответ не будет подписан и что запрошенные биты останутся на месте. Окончательный бросок затем уменьшает его обратно к желаемому типу.

Это действительно просто и элегантно, и я жалею, что не подумал об этом год назад. Спасибо всем, кто откликнулся раньше.
6