安全模乘无符号整数的最佳C方法是什么？

Question

假设您正在使用

具体来说，与std:：uint16_t相乘有时会失败得惊人，优化的构建会产生各种奇怪的结果。原因是什么？由于有符号整数溢出而导致未定义的行为。编译器正在基于不发生未定义行为的假设进行优化，因此开始从程序中删除代码块。具体的未定义行为如下：

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

原因是C的升级规则，以及你和现在几乎所有人一样，正在使用一个std:：numeric_限制的平台

一般问题的演示：

// 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'

当然，避免这种情况的方法是在相乘之前至少转换为无符号int。只有在无符号类型的位数正好等于int位数的一半的情况下才有问题。任何较小的值都会导致乘法无法溢出，就像std:：uint8_t；任何较大的值都会导致类型精确地映射到一个晋升级别，就像std:：uint64_t匹配无符号长或无符号长一样，这取决于平台。

但这真的很糟糕：它需要根据当前平台上int的大小知道哪种类型有问题。有没有更好的方法可以避免无符号整数乘法的未定义行为，而无需#if迷宫？




Answer 1

这里有一个相对简单的解决方案，对于比int窄的无符号类型，它强制升级到unsigned int，而不是int。我不认为任何代码是由升级生成的，或者至少没有比标准整数升级更多的代码；它只会强制乘法等使用无符号运算，而不是有符号运算：

#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 2

这篇文章关于C解决方案的情况下uint32_t*uint32_t乘法在系统中int是64位有一个非常简单的解决方案，我没有想到：32位无符号乘以64位导致未定义的行为？

这个解决方案，转化为我的问题，很简单：

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

简单地将1U包含在算术运算链的左侧，这样会将第一个参数提升到更大的秩无符号int和std:：uint16_t，然后依次类推。升级将确保答案是未签名的，并且请求的位仍然存在。最后的演员阵容将其缩减为所需的类型。

这真的很简单，很优雅，我希望我在一年前就能想到这一点。谢谢之前回应的每个人。

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

演示。

编辑：更简单：

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

演示。