我需要找出是否a*b >= c*d在a,b,c,d32位整数上签名(我机器上的'int').
是否可以仅使用32位有符号整数来比较那些没有溢出的产品,这样结果对于所有可能的值都是正确的？
我想过a/d >= c/b.
然而,它在'2*7> = 3*5'(假)上失败,因为'2/5> = 3/7'('0> = 0')为真.
目前,我将假设输入是有符号整数.
在这种情况下,我们想从检查标志开始.如果一方是负面的而另一方是正面的,这足以告诉我们结果(负面明显小于正面),所以我们已经完成了.
如果等式的两边都是正的或者都是负的,我们缓存结果的符号,然后去除符号,这样我们就可以处理乘法本身的无符号数.
一旦我们有无符号数,我们可以通过将每个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);
}
然后我们的结果是低+中<< 16 +上<< 32.因为我们处理的是32位整数,所以最简单的方法就是把mid它分成上半部分和下半部分.它的下半部分将被添加到lower其上半部分upper.然后,我们的结果将分布在两个(无符号)32位整数中,一个包含lower + mid_lower,另一个包含upper + mid_upper + carries.
从那里可以很简单地恢复我们在开始时存储的标志,然后比较上半部分,当且仅当它们相等时,比较下半部分.
如果你的号码开头是无符号的,那么你可以稍微跳过涉及标志的部分.