在C语言中进行位饱和加法（作业）

Question

我正在处理一个任务，但是我不知道如何实现它。我需要创建一个函数sadd(int x, int y)，它返回两个数字的和，除非它们相加会导致溢出（这时只需返回最大可能的int）。我已经想出了一些解决方案，涉及类型转换和条件语句，但是这些在解决方案中是不允许的。只能使用运算符~ ! ^ + << >> &和|。

- John C

---

问作业问题是可以的，但你应该标记它们为作业。 - Brian Roach

试一试，然后发布你所想到的东西。（正如布莱恩所说，家庭作业问题是可以的，但最好尽力而为，并发布你的代码。欢迎来到SO！） - John

没有 if/else，这将会很麻烦.. - Brendan Long

只要有一组有限的操作，你总是可以用蛮力方法找到解决方案... - aaz

@Brendan：当课程是计算机架构或类似的高级课程时，会询问类似的问题。低级指令集是有限制的。 - John

Answer 1

对于有符号数的加法，如果你把两个同符号的数字相加得到了一个不同符号的结果，则发生了溢出。由于涉及到范围，当你将两个不同符号的数字相加时，不可能发生溢出。

因此，你可以仅观察符号位（补码中最高位），使用异或运算来判断两个原始数字的符号是否不同，取反后得到“0”表示它们不同，“1”表示它们相同。

然后，你可以将结果与其中一个输入进行异或运算。如果它们相同，则得到“0”，如果它们不同，则得到“1”。

将这两个结果结合起来，如果两个输入相同但结果不同，则得到总体的“1”，否则得到“0”。

然后，你可以使用移位和或运算的组合来填充整个整数的值。假设你在32位整数中，只需设置最低31位即可获得最高值正整数。然后，你可以对任一输入的符号位进行类似的移位和或运算。对结果进行异或运算。如果输入为负，则给出最小值整数。

编辑：哦，使用溢出的位值，扩展到填满int，通过与你将返回的结果进行按位与来选择要返回的值，取反并与正常的加法结果进行按位与，然后将这两个结果进行或运算（或加法）。

完美：所有二进制逻辑，没有条件语句。我假设，因为这是作业，你不想要实际的代码？

---

九年后，我同意下面@gman的评论；为了仅使用允许的运算符来实现饱和加法，你必须依赖未定义的行为——上面的答案隐含地这样做了。

这样做的一个重要风险是编译器知道哪个行为是未定义的，并且可能在优化期间利用它。了解底层架构（例如它是补码，它执行有符号移位）并不足以预测编译器的输出。

可以进行强大的生产实现，但需要条件语句，因此无法回答此问题。

- Tommy

---

我已经编写好了代码，不确定是否适合在作业问题中添加完整的源代码答案。我给出的解释是否足够清晰？ - Tommy

也许不是，但你可以给他提示一下你的解决方案占用了多少条指令（假设使用MIPS指令集）。我们可以来比一下代码长度;-) - smci

这个答案是错误的。由于问题标记为 [tag:c]，根据 C 标准，有符号溢出是未定义行为，详情请参见此链接：https://dev59.com/OWMl5IYBdhLWcg3wsIyA。我编写了一段代码来检查溢出，通过检查符号变化来实现。但是，一旦编译器开始利用溢出是未定义的事实，它就会失败。 - gman

@gman，你认为只使用问题指定的运算符而不依赖于未定义行为编写饱和加法是可能的吗？这就是更改答案以说“你必须依赖于未定义行为”或仅仅删除它之间的区别。 - Tommy

从我所读的所有内容来看，我猜答案是否定的，但也许C/C++专家会更确定。 - gman

Answer 2

以下为ARM官网 (ARM信息中心) 有关内置函数的内容:

4.1 Compiler intrinsics

Compiler intrinsics are functions provided by the compiler. They enable you to easily incorporate domain-specific operations in C and C++ source code without resorting to complex implementations in assembly language.
The C and C++ languages are suited to a wide variety of tasks but they do not provide in-built support for specific areas of application, for example, Digital Signal Processing (DSP). Within a given application domain, there is usually a range of domain-specific operations that have to be performed frequently. However, often these operations cannot be efficiently implemented in C or C++. A typical example is the saturated add of two 32-bit signed two’s complement integers, commonly used in DSP programming. The following example shows a C implementation of saturated add operation

#include <limits.h>
int L_add(const int a, const int b)
{
    int c;
    c = a + b;         // Needs to be   c = a + (unsigned)b; to avoid UB
    if (((a ^ b) & INT_MIN) == 0)
    {
        if ((c ^ a) & INT_MIN)
        {
            c = (a < 0) ? INT_MIN : INT_MAX;
        }
    }
    return c;
}

在ISO C中，这个例子是不安全的；因为有符号整数溢出是未定义行为，所以你需要避免在检测它时引起它。使用c = a + (unsigned)b;可以避免这个问题，得到预期的二进制整数结果，因为2的补码加法与无符号二进制相同，但在C中unsigned类型具有明确定义的包装。

- Wayne Taylor

---

如果加法运算溢出，c = a + b; 就会出现未定义行为。在补码机器上，使用 c = a + (unsigned)b; 作为无符号数进行加法运算，然后再隐式转换回带符号数。这是与二进制补码有符号加法相同的操作，但在 C 中保证可以包装。 - Peter Cordes