正数相乘得到负数的整数

Question

我正在通过阅读Stroustrup的《C++程序设计原理与实践》来学习C++。

在关于前置条件和后置条件的部分，有一个函数的以下示例：

int area(int length, int width)
// calculate area of a rectangle;
// pre-conditions: length and width are positive
// post-condition: returns a positive value that is the area
{
    if (length<=0 || width <=0) 
        error("area() pre-condition");

    int a = length*width;

    if (a<=0) 
        error("area() post-condition");

    return a;
}

让我感到困惑的是这段代码的任务：

找到一对数值，使得此版本的area函数的前置条件成立，但后置条件不成立。

是否存在这样的整数数值，其前置条件可以成立但后置条件不成立？

- Pavel_K

---

没有，除非是导致未定义行为的值。幸运的是，有一种方法可以检查这个问题。请参考此链接：https://dev59.com/3nVC5IYBdhLWcg3wvTxa - g24l

Answer 1

是否存在整数值，其前置条件是可以的但后置条件不可行？

是的，有许多输入值可能会导致后置条件失败。例如：

int a = length*width;

当length*width超出正数int范围(std::numeric_limits<int>::max())时，编译器会为此情况产生负值。

---

正如其他人在他们的答案中指出的那样，length*width超出了]0-std::numeric_limits<int>::max()[的范围实际上是未定义的行为，并且后置条件仅仅是没用的，因为对于a可以期望任何值。

修复这个问题的关键点，在@Deduplicator的答案中给出，需要改进前置条件。

---

作为Bjarne Stroustrup给出这个例子的原因的一支长矛:

我认为他想指出这样的未定义行为可能会导致后置条件中出现意外的负值，并且会对使用前置条件检查的天真假设产生令人惊讶的结果。

- πάντα ῥεῖ

---

需要更正。即使溢出产生正值，后置条件也不成立。 - Anonymous Coward

@JoseAntonioDuraOlmos：请问，正值<=0是如何实现的？ - Lightness Races in Orbit

@LightnessRacesinOrbit，确实，正值不是小于等于0的。但请记住，函数的后置条件是“返回一个正面积值”。如果乘法运算溢出为正整数，则结果不是面积。 - Anonymous Coward

例如，4600046000是2116000000，在范围内。将其增加到4700047000，你得到-2085967296，超出了范围。继续增加到66000，你得到61032704，这是正数，但不是真实面积4356000000。 - corsiKa

@JoseAntonioDuraOlmos 感谢您指出。后置条件可能无法捕捉到所有情况，但这不是首要问题。 - πάντα ῥεῖ

Answer 2

不，根据标准C++的定义行为范围内，没有任何值会违反后置条件。然而，存在一些数值仍然可能导致函数执行错误，即这些数值过大以至于它们的乘积无法适应整数。尝试传入200'000和15'000。

由于大多数编译器实现C++的方式，您可能会看到后置条件被违反，但实际上您观察到的是由于整数溢出而产生的未定义行为。

- Sebastian Redl

Answer 3

答案是他的前置条件检查不完整。尽管它太严格了。
他没有包括一个检查，即产品可以被表示而不会导致UB：

int area(int length, int width) {
    // calculate area of a rectangle
    assert(length >= 0 && width >= 0 && (!width
        || std::numeric_limits<int>::max() / width >= length));
    int a = length * width;
    assert(a >= 0); // Not strictly neccessary - the math is easy enough
    return a;
}

- Deduplicator

Answer 4

我想到的是带符号整数溢出。这是未定义的行为，但可能会产生负值。
尝试使用std::numeric_limits<int>::max()和2。

- cadaniluk

Answer 5

如果假设您正在使用16位计算机，则int = 2B最大值为+32767，因此如下所示：

{
    length = 500, width = 100;
    if (length<=0 || width <=0) error("area() pre-condition");
    int a = length*width;   // a = 500 * 100 = 50000
    if (a<=0) error("area() post-condition");
    return a;
}

现在最终的值将是a = -17233，因为它变成了负值。所以第二个条件为假。

这完全取决于范围。

- Kamaldeep singh Bhatia

---

如果这是一台32位计算机，并且您正在使用“int”，则最大值不应该是“32,767”，而应该是“2,147,483,647”。 - Hatted Rooster

是的，但我已经在那方面练习过了，我认为从概念上讲并没有错吧？ - Kamaldeep singh Bhatia

让我感到有趣的是，印度仍然使用在DOSBox中模拟的16位编译器来教授C++。自从20世纪90年代初以来，这种环境还有什么相关性呢？_25年前_？？ - Lightness Races in Orbit

@JameyD：关于“32位”或“64位”计算机的定义并不唯一，而且计算机的“位数”与类型int的大小之间也没有一致的关系。一个32位的计算机通常会有32位的int，但它可能是16位，尽管这很少见。一个64位的计算机通常会有32位的int。 - Keith Thompson

@kamaldeepsinghbhatia：哪种数据类型？int的大小取决于编译器，并且通常由ABI规定。 int32_t的大小始终精确为32位，通常为4个字节。根据定义，sizeof（char）== 1。 - Keith Thompson

Answer 6

INT_MAX 在所有符合标准的编译器中，当用于长度和宽度时都无法满足后置条件。

有人可能会说，由于标准保证 INT_MAX>=32767，那么 INT_MAX*INT_MAX 总是大于 INT_MAX，因此不能表示为一个能够容纳最大值为 INT_MAX 的 int。
这是一个好的观点，实际上在大多数编译器中你会遇到溢出。

但为了涵盖所有情况，我们需要知道 C++标准 规定：

3.4.3
1 未定义的行为
使用不可移植或错误的程序结构或错误的数据时，对于这种情况，国际标准没有强制要求的行为

2 注意 可能的未定义行为范围从完全忽略具有不可预测结果的情况到在环境中表现出文档化的特征的翻译或程序执行行为（无论是否发出诊断消息），到终止翻译或执行（发出诊断消息）。

3 例子 一个未定义行为的例子是整数溢出时的行为。

因此，这比仅仅得到面积的正确值更加严重。当将 INT_MAX 用于长度和宽度（或任何其他组合的结果不可表示）时，不能保证编译后的程序会做什么。任何事情都可能发生；从可能的溢出或崩溃到不太可能的磁盘格式。

- Anonymous Coward

---

我同意这种编程方式是不好的做法，但实践中很容易预测当前编译器会做什么。一个激进的编译器仍然无法优化掉对a<0的检查，因为它需要处理正负乘积为负数的情况。像(x+1) > x这样的检查对于有符号整数完全被优化掉，但对于无符号整数则不能。还有@JimJim2000：请参见http://teaching.idallen.com/dat2343/10f/notes/040_overflow.txt了解无符号溢出和有符号溢出术语的区别。 - Peter Cordes

http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html解释了为什么编译器这样做很有帮助：例如，可以为循环计数器生成更高效的代码。 - Peter Cordes

Answer 7

值类型的位表示溢出时，值的乘积是未定义的，因为溢出的比特数可能超过1。因此，您可能会得到一个正号或负号位，并且丢失的比特数是可变的。

示例1：INT_MAX * 2：结果是正确的，但由于高位表示符号位，因此它对其类型来说不是正确的表示。

示例2：INT_MAX * 4：1个比特位被溢出丢失，符号位与前面的示例一样不正确。

示例3：(INT_MAX + 1) * 2 = 0：由于所有设置的比特位都溢出了，但符号是正确的。

我使用8位二进制表示使其更易于阅读，以说明为什么会发生这种情况。

0111 1111              // Max positive signed value
+1
1000 0000              // Sign bit set but binary value is correct
*2
0000 0000              // Upper bit is lost due to overflow

在这种情况下，软溢出会导致信息没有丢失，但表示不正确。而硬溢出则意味着该位在结果中不再存在。

两种溢出的区别在于如何检测溢出。通常，硬溢出将由硬件检测，并且软件处理起来非常容易。然而，软溢出可能需要软件显式测试溢出条件，因为硬件通常无法识别整数计算操作中的符号位。

运行时库如何处理溢出取决于库。大多数库会忽略它，因为这样做更快，而其他库可能会抛出错误。 未定义的行为并不意味着它可能会格式化您的磁盘。数学运算的结果不会以任何方式改变代码流程，除非代码逻辑规定。它可以忽略溢出或尝试以某种方式处理它。标准没有规定如果代码或硬件试图处理该问题应采用哪种方法。

基本上有3种可能发生的情况。 1. 溢出被忽略，返回值无效。 2. 运行时库忽略了溢出，但硬件抛出一个被忽略的错误，导致正在运行的代码硬性失败。在这种情况下，完全由操作系统决定下一步发生的事情。破坏数据会是一个很差的设计决策。 3. 溢出由运行时库处理，必须确定最佳处理方式。通常，这意味着给代码捕获错误并处理它的机会，或通过尽可能优雅地关闭代码来处理它。

- Brian Nebeker

Answer 8

自从C++11以来，您可以测试一个布尔值：

std::numeric_limits<int>::is_modulo

如果这个值为true，那么有符号算术会以环绕的方式运行，并且原始代码中没有未定义的行为。确实可能产生负值，因此原始代码中的测试是有意义的。

有关is_modulo的进一步讨论，请参见此处。

- M.M

Answer 9

基本上，在乘法中正值会导致正值结果，但这些结果可能实际上不适合结果类型。

你的前置条件不完整，后置条件也无效。你不仅可以得到负值，还可以得到比输入值小的正值，只需要足够大的输入值使得环绕超过零，即长环绕。

你可以使用this：

bool multiplication_is_safe(uint32_t a, uint32_t b) {
    size_t a_bits=highestOneBitPosition(a), b_bits=highestOneBitPosition(b);
    return (a_bits+b_bits<=32);
}

为了防止溢出，您需要使用其他检查来避免假阳性。

或者，如果性能不是太重要，您可以使用 MPZ 库。如果性能很关键，您希望为具有溢出标志的 CPU 编写汇编代码，则可以这样做。可能您的编译器也可以为您进行检查，例如 G++ 具有 fno-strict-overflow 或在前提条件检查之后转换为 unsigned int。

无论如何，大多数解决方案实际上都不能解决您的问题，即结果将是 foo，也就是说，您可能得到的面积比实际结果小。

因此，您唯一安全的选择是仅允许安全的乘法，如本文所示，这样您会错过一些东西，但并不多。

- g24l