什么是最安全的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被提升为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迷宫而避免使用无符号整数乘法时的未定义行为？

- Myria

---

@TC：听起来非常低效。64位乘法可能会很慢。 - Ben Voigt

一个后续问题：是什么规则/提升使得 x *= x; 将 uint16_t 提升为 int32_t？我在标准中找到了一些提升规则，但无法将它们精确地映射到这个问题上。 - towi

@BenVoigt 在标准中存在一条复杂的路径，它指出对于某些数据值，两个无符号短整型数相乘并得到无符号短整型结果会产生未定义行为，因为存在有符号整数溢出。标准中还有更直接的陈述，即对于相同的无符号数据类型进行算术运算所产生的结果不能溢出，并且结果就像使用了模算术一样，这是任何合理程序员都期望的。标准自身存在冲突。 - amdn

uint8_t(a) * uint8_t(b)并没有对无符号类型进行算术运算，因此不适用于控制无符号算术的子句。虽然意外，但是这是真的。 - Ben Voigt

当你需要像这个问题的答案那样复杂的解决方案来为标准的简单语义解释添加句法糖时，丹麦的情况就有些可疑了。 - amdn

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

Demo.

- T.C.

---

我认为可能有效的方法是通过 std::numeric_limits 检测 <decltype(a)>::max() > <decltype(a * b)>::max() / <decltype(b)>::max()（进行适当的强制转换），因为 max 是一个 constexpr 函数。如果是这样，将每个参数转换为 typename std::make_unsigned<decltype(+a))>::type 而不仅仅是 unsigned int。这应该可以捕捉到每一种情况。（make_unsigned 中的一元 + 用于确定提升类型。）无条件地将其转换为提升类型的 make_unsigned 也是有效的，并且在健全的平台上应该同样快。 - Myria

@Myria 关于在提升类型上无条件使用 make_unsigned 的观点很好。仍然需要保持 enable_if，以便在传递有符号类型时不起作用。 - T.C.

Answer 2

本文讨论了一个C语言的解决方案，用于处理在64位系统中int为64位时，uint32_t * uint32_t乘法的情况。这个方案非常简单，但我之前没有想到： 32 bit unsigned multiply on 64 bit causing undefined behavior？

将该解决方案应用于我的问题，则变得简单：

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

将1U简单地放到算术操作链的左侧，会将第一个参数提升到较大的unsigned int和std::uint16_t等级，然后一路传递下去。该提升将确保答案既是无符号的，又保留所需的位数。最后的强制类型转换将其还原为所需类型。

这实在是非常简单且优雅，我真希望我一年前就能想到它。感谢之前回复我的所有人。

- Myria

---

此外，这个解决方案适用于C和C++，并避免了所有的模板疯狂。 - Nayuki

@Nayuki 是的，已经在答案中添加了 C 语言版本。 - Myria

Answer 3

这里有一个相对简单的解决方案，它将无符号类型强制转换为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;
}

- rici

---

很酷，我喜欢这个。在我看来，第6行应该写成typename std::make_unsigned<integer>::type而不是"unsigned"。此外，为了强制升级，您也可以使用一元的+；换句话说，+integer()。当我写问题时，我对问题有了相当好的理解，只是不太懂这些很酷的模板技巧，感谢您和@T.C. =) - Myria

@Myria 这里不能使用 std::make_unsigned<integer>::type。如果你真的想使用它，需要改为 std::make_unsigned<decltype(+a)>::type。此外，这将编译有符号类型，这可能不是一个好主意，所以你需要在某个地方加上 enable_if：template<typename integer> using promoted = typename std::enable_if<std::is_unsigned<integer>::value, typename std::conditional</*...*/>::type>::type;。 - T.C.

@t.c. 只需通过添加 &&!is_signed<intger> 来更改布尔表达式： - rici

@rici如果您这样做，它仍会编译（尽管不再强制转换）。我认为在不打算强制使用无符号算术时调用类似于promote的东西应该被视为一个错误，因此最好在编译时进行诊断。 - T.C.