将模块化安全地乘以无符号整数的最佳C++方法是什么？

Question

比方说,你正在使用<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被提升为32位带符号算术的溢出.signed int0xFFFF * 0xFFFF

演示一般问题:

// 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迷宫？

Answer 1

也许有一些模板元编程与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;
}

演示.

编辑:更简单:

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

演示.

Answer 2

这是一个相对简单的解决方案,它强制促销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;
}

Answer 3

关于uint32_t * uint32_t在int64位系统上乘法的C解决方案的这篇文章有一个我没想过的非常简单的解决方案:64位无符号乘法导致未定义的行为？

解决我的问题的解决方案很简单:

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

只要涉及1U的算术运算链的左侧这样将促进的第一个参数的更大的排名unsigned int和std::uint16_t,然后等环比下滑.促销将确保答案既未签名且请求的位仍然存在.然后最终的铸件将其缩减回所需的类型.

这真的很简单和优雅,我希望我一年前就想到了它.谢谢所有回复的人.