9

编辑公共卫生警告 - 这个问题包括关于未定义行为的错误假设。请参阅已接受的答案。

在阅读了最近的博客文章后，我一直在思考在 C 和 C++ 代码中避免所有标准未定义假设的实用性。这是从 C++ 中截取的片段，用于进行无符号 128 位加法...

void c_UInt64_Pair::operator+= (const c_UInt64_Pair &p)
{
  m_Low  += p.m_Low;
  m_High += p.m_High;

  if (m_Low < p.m_Low)  m_High++;
}

这显然依赖于关于溢出行为的假设。显然，大多数机器都可以支持正确类型的二进制整数（尽管可能是从 32 位块构建或其他），但优化器显然越来越有可能利用此处的标准未定义行为。也就是说，m_Low < p.m_Low条件可以通过的唯一方法是如果m_Low += p.m_Low溢出，这是未定义的行为，因此优化器可以合法地确定条件总是失败。在这种情况下，这段代码就被破坏了。

问题是，因此...

如何在不依赖未定义行为的情况下编写上述合理有效的版本？

假设您有一个适当的 64 位二进制机器整数，但是您有一个恶意编译器，它总是以最坏的可能（或不可能）的方式解释您的未定义行为。另外，假设您没有一些特殊的内置、内在、库或任何东西可以为您做。

编辑 小说明 - 这不仅仅是检测溢出，还确保 m_Low 和 m_High 都以正确的模 2^64 结果结束，这也是标准未定义的。

4

2 回答 2

17

来自 C++ 1998 标准 3.9.1(4)：“声明为无符号的无符号整数应遵守算术模 2^n 的定律，其中 n 是该特定整数大小的值表示中的位数。” 请注意，这里的“整数”指的是任何整数类型，而不仅仅是int.

因此，假设这些是无符号整数，如类型中的“UInt64”所暗示的，这是 C++ 中定义的行为，应该按预期工作。

于 2010-08-25T19:37:04.120 回答
0

如果你想要一个真正有效的方法，你将不得不用 C 或 C++ 以外的东西编写代码。为了获得合理的效率，您必须确保永远不会发生溢出，并检测并补偿何时会发生。

基本上，对于每个 64 位组件，您需要使用低 63 位和最高位分别计算加法。从这些单独的计算中，您可以计算出 64 位总数是多少，以及是否有进位。

然后，当您执行高位 64 位加法时，如果有进位，则添加进位。如果由此产生进位，那么您的 128 位变量已经溢出，您需要触发异常，或者以其他方式处理这种情况。

于 2010-08-25T19:36:40.493 回答