c++ - 比较两个整数乘积而不会溢出

Question

我需要确定 a*b >= c*d 其中 a,b,c,d 是否是带符号的 32 位整数(我的 'int'机)。

是否可以仅使用 32 位有符号整数来比较这些产品而不会溢出，以便结果对于所有可能的值都是正确的？

我想到了 a/d >= c/b。

但是它在 '2*7 >= 3*5'(假)时失败，因为 '2/5 >= 3/7'('0 >= 0')为真。

Answer 1

目前，我假设输入是有符号整数。

既然如此，我们要从检查标志开始。如果一侧为负，另一侧为正，这足以告诉我们结果(负值明显小于正值)，所以我们完成了。

如果等式的两边都是正数或都是负数，我们缓存结果的符号，然后去掉符号，这样我们就可以处理乘法本身的无符号数。

一旦我们有了无符号数，我们就可以通过将每个 32 位整数视为两个不同数字的总和来进行乘法运算，一个代表输入数字的低位，一个代表高位。因此，您会将 a、b、c 和 d 中的每一个转换为两个只有 16 位有效位的数字位。所以，对于左侧，我们有:

al = a & 0xffff;
au = a >> 16;

bl = b & 0xffff;
bu = b >> 16;

所以:

a * b 

...等同于:

(al + au << 16) * (bl + bu << 16)

并使用分配属性，我们可以将其转化为:

al * bl + au<<16 * bl + al * bu<<16 + au<<16 * bu<<16

由于 a * (b * c) = (a * b) * c，我们可以在 之后进行所有位移我们做其他乘法，所以这变成:

al * bl +            // we'll call this intermediate result "lower"
(au * bl) << 16 +
(al * bu) << 16 +    // we'll call the sum of these two "mid" 
(au * bu) << 32      // we'll call this one "upper"

现在重要的一点是:我们的位掩码确保每个乘法步骤的输入只有 16 个有效位，因此每个中间结果将只有 32 个有效位，因此每个结果都适合一个 32 位整数而不溢出。

从那里，我们必须对各项进行求和。这有点不平凡，但仍然相当容易处理。首先，我们必须弄清楚一项的总和是否会产生进位。一种方法是这样的:

bool carry(unsigned a, unsigned b) { 
    return a > (std::number_limits<unsigned>::max() - b);
}

然后我们的结果是 lower + mid<<16 + upper << 32。因为我们处理的是 32 位整数，所以可能最简单的方法是将 mid 分成 upper 和下半部分。它的下半部分将被添加到lower，它的上半部分将被添加到upper。然后，我们的结果将分布在两个(无符号)32 位整数中，一个包含 lower + mid_lower，另一个包含 upper + mid_upper + carries。

从那里恢复我们在开始时存储的符号是一件简单的事情，然后比较上半部分，当且仅当它们相等时，比较下半部分。

如果您的数字一开始是无符号的，那么您可以稍微跳过涉及符号的部分。