sumar - ¿Cuál es la mejor forma en C++ de multiplicar de forma segura los enteros sin signo modularmente?

suma resta multiplicacion y division de numeros complejos en c++

Question

Digamos que está utilizando <cstdint> y tipos como std::uint8_t y std::uint16_t , y desea realizar operaciones como += y *= en ellos. Le gustaría que la aritmética en estos números se envuelva modularmente, como es típico en C / C ++. Esto normalmente funciona, y encuentra que funciona experimentalmente con std::uint8_t , std::uint32_t y std::uint64_t , pero no std::uint16_t .

Específicamente, la multiplicación con std::uint16_t veces falla de manera espectacular, con compilaciones optimizadas que producen todo tipo de resultados extraños. ¿La razón? Comportamiento indefinido debido al desbordamiento de enteros con signo. El compilador se está optimizando basándose en el supuesto de que no se produce un comportamiento indefinido y, por lo tanto, comienza a eliminar trozos de código de su programa. El comportamiento indefinido específico es el siguiente:

std::uint16_t x = UINT16_C(0xFFFF);
x *= x;

El motivo son las reglas de promoción de C ++ y el hecho de que usted, como casi todos los demás en la std::numeric_limits<int>::digits == 31 , está utilizando una plataforma en la que std::numeric_limits<int>::digits == 31 . Es decir, int es de 32 bits (los digits cuentan los bits pero no el bit de signo). x se promueve a signed int , a pesar de no estar firmado, y 0xFFFF * 0xFFFF desborda para aritmética firmada de 32 bits.

Demostración del problema general:

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

Obtendrás un bonito error:

main.cpp:11:55: runtime error: signed integer overflow: 65535 * 65535
    cannot be represented in type ''int''

La forma de evitar esto, por supuesto, es lanzar al menos unsigned int antes de multiplicar. Solo el caso exacto donde el número de bits del tipo sin signo exactamente igual a la mitad del número de bits de int es problemático. Cualquier menor haría que la multiplicación no se pudiera desbordar, como con std::uint8_t ; un mayor tamaño daría como resultado que el tipo se asignara exactamente a uno de los rangos de promoción, como si std::uint64_t emparejara unsigned long unsigned long long unsigned long o unsigned long long según la plataforma.

Pero esto realmente apesta: requiere saber qué tipo es problemático según el tamaño de int en la plataforma actual. ¿Hay alguna mejor manera de evitar el comportamiento indefinido con la multiplicación de enteros sin signo sin #if mazes?

Answer 1

Alguna plantilla de metaprogramación con SFINAE, tal vez.

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

Demo

Edición : más simple:

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

Demo

Answer 2

Aquí hay una solución relativamente simple, que obliga a una promoción a unsigned int lugar de int para unsigned type más estrecho que un int . No creo que ningún código sea generado por promote , o al menos no más código que la promoción de enteros estándar; solo forzará la multiplicación, etc., para usar operaciones sin firma en lugar de las firmadas:

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

Answer 3

Este artículo sobre una solución en C para el caso de la multiplicación uint32_t * uint32_t en un sistema en el que int es de 64 bits tiene una solución realmente simple en la que no había pensado: ¿ 32 bits sin signo multiplicar en 64 bits causando un comportamiento indefinido?

Esa solución, traducida a mi problema, es simple:

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

El simple hecho de involucrar 1U en el lado izquierdo de la cadena de operaciones aritméticas como esa promoverá el primer parámetro al rango más amplio de unsigned int y std::uint16_t , y así sucesivamente en la cadena. La promoción garantizará que la respuesta esté sin firmar y que los bits solicitados permanezcan presentes. El último lanzamiento luego lo reduce de nuevo al tipo deseado.

Esto es realmente simple y elegante, y desearía haberlo pensado hace un año. Gracias a todos los que respondieron antes.