主页 / 问题 / 1587043
Accepted
Yulia
Asked:2024-07-13 17:29:46 +0800 CST2024-07-13 17:29:46 +0800 CST

2^32 模加法的实现和溢出问题？

  • 772

需要实现模2^32的加法。

首先想到的是简单地添加两个数字（uint32_t）的想法；之后就会溢出，但结果是4个低字节，应该是模2^32的加法结果。

但这不会一不小心就变成“未定义行为”吗？如果是这样，如何以不同的方式实现这种添加？

c++

3 个回答

  1. Best Answer

    根据文档，对所有无符号类型执行的计算均以 2ⁿ 为模执行，其中n是位数，并且不会导致未定义的行为（当然除以零除外）。

    因此，您所要做的就是uint32_t按照您的预期使用类型。

    但是使用有符号类型（例如，int32_t）更加危险，因为在这种情况下溢出是未定义的行为。

    不要忘记将文字（如 1）强制转换为 type uint32_t，否则编译器可能会推断结果表达式不是您想要的类型（例如，有符号的）。

    但是，某些编译器具有强制有符号类型遵守与无符号类型相同的规则的编译开关。例如，gcc 有一个选项-fwrapv.但这将使您的代码不再可移植。

    添加：评论中的讨论使我确信，uint32_t在特殊情况下使用 taki 可能会导致未定义的行为。要检查您的情况是否非异常，请插入以下断言：

    #include <cstdint>
#include <type_traits>

static_assert(std::is_unsigned_v<decltype(+(uint32_t)0)>);

    对于所有“正常”系统，此断言通过。

    如果你的系统很奇特怎么办？

    • 对于 MSVC 来说，该系统并不陌生。
    • 对于 GCC/Clang，使用 key -fwrapv，它会阻止 UB。
    • 如果系统上的大小int大于 32 位，请读取 中的所有内容unsigned int，并在最后（一次）剪掉不必要的位。
    • 如果您的系统上的大小long是 32 位，则以 unsigned long 计数（但您的系统必须是非奇异的）
    • 如果大小int小于32位且大小long较大，则读入unsigned long，在最后（一次）截掉不需要的位。

    了解有哪些奇异病例以及它们来自何处。事实上，在加法之前，C++ 将尺寸较小的数字类型减少int为类型intor unsigned int，并将字符类型（例如char32_t）减少为类型int, unsigned int, long int, unsigned long int, long long intor unsigned long long int。

    在正常系统中，它是或uint32_t的别名，不会出现任何问题。但该标准并不禁止做一些愚蠢的事情，例如在 上定义别名，该别名有权被带到或 那里。unsigned intunsigned long intuint32_tchar32_tintlong int

    （整个幻象的确切规则在标准第 7.3.7 章中有描述。）

    是的，在一个奇异的系统上可能没有类型uint32_t。

    建议的断言只是检查整型提升 ( ) 后类型uint32_t( ) 的值至少仍然是无符号类型 ( )。(uint32_t)0+(uint32_t)0std::is_unsigned_v<decltype(...)>

    • 2

  2. static_cast<uint32_t>(static_cast<uint64_t>(a) + static_cast<uint64_t>(b))uint32_t将执行模2 32类型的两个操作数的加法，没有未定义的行为。编译器有足够的信息来在所有流行的处理器上执行添加到单个汇编指令中 - 强制转换不会在代码中插入额外的指令。

    • 1

  3. 它不会，因为额外的位根本不会保留在内存中，并且对于无符号我们将得到零。未定义的行为是指离开链接、指针、迭代器、向量重定位等的可见区域。

    • -1

相关问题