gcc 溢出时给出最低64位的算法

kpbpu008  于 12个月前  发布在  其他
关注(0)|答案(3)|浏览(185)

在C中,无符号整数运算在溢出时会绕回,而有符号运算在溢出时是未定义的。我想有64位整数运算(+,-,*),这样在溢出时结果是最低的64位。这可能吗?
我不想要一个环绕的结果。我所寻找的是等效于将整数转换为128位类型,执行操作,取最低的64位并转换回64位类型。

mbyulnm0

mbyulnm01#

扩展以前的答案:虽然绕回是简单地计算模264是正确的,但这种计算可能会以意外的符号结束!仅考虑四位:

1100 * 0011 = 10 0100 ≡ 0100 mod 10000
 12  *  3   =    36   ≡   4  mod   16
 -4  *  3             ≡   4  mod   16

字符串
数学上到目前为止是正确的,但是负整数和正整数的结果是正的。一方面,这 * 可以 * 用于检测溢出:

if((f1 ^ f2 & MSB) != (p & MSB))
{
    // overflow!
}


另一方面,你也可以调整标志:

1100 * 0011 = 10 0100 ≡  100  mod 1000
 12  *  3   =    36   ≡   4   mod  8
 -4  *  3             ≡   4   mod  8   // subtract 8!
 -4  *  3             ≡  -4   mod  8   // still correct!
1100 * 0011           ≡ 1100  mod 1000


因此,您实际上可以做到:

#define MSB = ((uint64_t)1 << 63)

int64_t mul(int64_t x, int64_t)
{
    uint64_t p = (uint64_t)x * (uint64_t)y;
    p &= MSB;
    // subtracts MSB, if differing sign bits, else 0:
    p -= (uint64_t)x ^ (uint64_t)y & MSB;
    return p; // implicit conversion
}


godbolt-和这个变种的缺点,它的权利,太:虽然符号位保持正确的两个值都在绝对小现在可以产生一个值巨大的绝对.
你更喜欢哪一个?)

aiazj4mn

aiazj4mn2#

首先将操作数强制转换为无符号类型(大小相同),执行操作,然后强制转换回有符号类型。
+-的证明很容易。*的证明不确定,但它似乎也给予了正确的结果。
GCC和Clang也有__builtin_{add,sub,mul}_overflow,它总是绕回,也会报告是否发生溢出。它们可以处理任何整数类型。

int a = 10, b = 20, result;
bool overflowed = __builtin_add_overflow(a, b, &result);

字符串

ndh0cuux

ndh0cuux3#

无符号整数算术被定义为wrap。对于w位整数,这意味着计算(+,-,*)是以2^w为模执行的。这完全等同于总是取结果的低w位,因此执行wrapped加法,减法和乘法保证在低w位的数学正确性。因此,如果您只关心结果的低W位,则不需要执行具有较大位宽的计算。
有符号整数比较复杂。当将一个有符号整数转换为一个相同宽度的无符号整数时,需要加上2^w的倍数,以使该数字进入一个可表示的范围。实际上,对于二进制补码机器,这意味着对于负数加上2^w,否则加上0。因此,将一个有符号整数转换为无符号整数总是保持模2^w的值(即使在非二进制补码机器上!)。
因此,如果你取两个有符号整数,将它们转换为无符号,然后进行数学运算,得到的无符号数将等价于有符号结果模2^w。如果你然后将这个结果转换回有符号整数,你 * 应该 * 得到一个等于期望的有符号结果的值;使用无符号算术将避免任何未定义的溢出。
注意最后一句中使用了“should”。这里的小问题是,如果无符号结果超出了有符号数的范围,(即在二进制补码系统上是>= 2^(w-1)),那么将其转换回有符号整数在技术上是实现定义的。实际上,由于现在几乎所有的机器都使用二进制补码,结果会如你所愿。

相关问题