c - 在 C (HW) 中仅使用按位运算符的饱和有符号整数加法

Question

对于家庭作业，我必须用 C 编写一个函数，将两个有符号整数相加，但如果存在正溢出则返回 INT_MAX，如果存在负溢出则返回 INT_MIN。我必须遵循非常严格的操作符限制。所有整数都是二进制补码形式，右移是算术，整数大小是可变的(我可以用 sizeof(int)<<3 找到它)。我不能使用条件、循环、比较运算符或强制转换。我只能使用按位和逻辑运算符、加法和减法、相等测试以及整数常量 INT_MAX 和 INT_MIN。

我知道如果两个输入具有相同的符号并且结果具有不同的符号，则可以检测到溢出。我已经到了有一个标志显示等式是否溢出的地步。我不知道如何从那里到最终产品。这是我到目前为止:

int saturating_add(int x, int y){
    int w = sizeof(int)<<3;
    int result = x+y;
    int signX = (x>>w-1)&0x01;//Sign bit of X
    int signY = (y>>w-1)&0x01;//Sign bit of Y
    int resultSign = (result>>w-1)&0x01; //Sign bit of result
    int canOverflow = ~(signX ^ signY); //If they're the same sign, they can overflow
    int didOverflow = (resultSign^signX)&canOverflow; //1 if input signs are same and result sign different, 0 otherwise

}

我正在尝试遵循 Bitwise saturated addition in C (HW) 中显示的答案，但我被困在我必须用相同的位填充整数的部分，除了符号位(1 到 0111..11，0 到 0000.00)。我不知道“类次和 OR 的组合”是什么。

Answer 1

我想你误解了答案。你应该做的是将符号位扩展到 全部 位，包括 MSB。这可以通过获取持有符号位的 int 来实现，例如didOverflow ，并在其补数上加 1。

然后你会发现在发生溢出的情况下应该返回哪个溢出值。这可以通过异或运算来完成 INT_MAX带扩展 signX (或 signY ，两者都可以)。让我们称这个值 overflow .最后，更改 overflow和 result像这样:

overflow := (extended didOverflow) AND overflow
result := (NOT (extended didOverflow)) AND result

现在，在这些分配之后，如果扩展 didOverflow是 1...1，然后 overflow显然会保持不变。 result ，另一方面，将等于 0。

但如果 didOverflow是 0...0，则相反: overflow现在是 0，而 result保持不变。

在第一种情况下(其中 didOverflow 是 1...1，表示存在溢出)， overflow OR result等于 overflow .在第二种情况下(我们没有溢出)， overflow OR result等于 result .所以无论哪种方式， overflow OR result会给我们正确的值。