c bit-manipulation addition saturation-arithmetic

C 中的按位饱和加法 (HW)

发布于 2024-10-21 19:39:06 字数 210 浏览 1 评论 0原文

我正在做一项作业，但我不知道如何实现它。我必须创建一个函数 sadd(int x, int y) ，它返回相加的数字，除非它溢出（然后只返回最大可能的 int）。我已经能够提出一些涉及强制转换和条件语句的解决方案，但解决方案中不允许这些。仅运算符 ~ ! ^ + << >>> & 和 |。

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

时光沙漏 2024-10-28 19:39:06

对于有符号数的加法，如果将两个相同符号的数字相加并得到不同符号的结果，就会发生溢出。由于涉及范围，两个不同符号的数相加时不可能产生溢出。

因此，您可以做的是 - 仅观察符号位（二进制补码中最重要的一位） - 使用异或来确定两个原始数字的符号是否不同，对其进行补码，以便在以下情况下得到“0”：它们是不同的，“1”表示相同。

然后，您可以对结果与输入之一使用异或。如果它们相同，则给出“0”；如果不同，则给出“1”。

如果两个输入相同但结果不同，则这两个结果加在一起得到总体“1”，否则为“0”。

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

编辑：哦，并使用是否存在溢出的位值，扩展以填充 int，通过将其与如果存在溢出则返回的结果进行相加来选择要返回的值，对其进行补足并与正常情况进行相加加法结果，然后将两者或（或相加）在一起。

Presto：所有二进制逻辑，没有条件。我认为，因为这是家庭作业，您不需要实际的代码？

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

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

稳健的生产实现是可能的，但需要条件语句，因此不会回答这个问题。

For addition of signed numbers, overflow has happened if you add two numbers of the same sign and get a result with a different sign. Because of the ranges involved, it is impossible to generate overflow when adding two numbers of different signs.

So, what you can do is — watching the sign bit only (the most significant one in two's complement) — use exclusive OR to get to whether the two original numbers differed in sign, complement that so that you've got '0' if they were different, '1' for the same.

You can then use exclusive OR on the result versus one of the inputs. That'll give '0' if they were the same, '1' if they were different.

And those two results together to get an overall '1' if the two inputs were the same but the result was different, '0' otherwise.

You can then use a combination of shifts and ORs to fill an entire integer with that value. Supposing you're in a 32 bit integer, just set the lowest 31 bits to get the highest value positive integer. What you can then do is a similar sets of shifts and ORs on the sign bit of either of the inputs. Exclusive OR the results. That'll instead give the lowest value integer if the inputs were negative.

EDIT: oh, and use the bit value of whether there was overflow, extended out to fill the int, to select what value to return by anding it with the result you would return if there were overflow, complementing it and anding it with the normal additive result, then oring (or adding) the two together.

Presto: all binary logic, no conditionals. I assume, because it's homework, that you don't want actual code?

Nine years later, I agree with the comment of @gman below; in order to implement saturating addition using only the permitted operators, you've got to rely on undefined behaviour — and the answer above implicitly does so.

A substantial risk with that is that compilers know which behaviour is undefined and may exploit that during optimisation. Knowledge of the underlying architecture (e.g. that it is two's complement, that it does signed shifts) is not sufficient to predict a compiler's output.

A robust production implementation is possible, but would require conditional statements and therefore would not answer this question.

回复收藏 0 原文

仅此而已 2024-10-28 19:39:06

来自 ARM 网站 (ARM 信息中心）内在函数：

4.1 编译器内部函数
编译器内在函数是编译器提供的函数。它们使您能够轻松地将特定于域的操作合并到 C 和 C++ 源代码中，而无需求助于汇编语言中的复杂实现。
C 和 C++ 语言适用于各种任务，但它们不提供对特定应用领域（例如数字信号处理 (DSP)）的内置支持。
在给定的应用程序域内，通常存在一系列必须频繁执行的特定于域的操作。然而，这些操作通常无法在 C 或 C++ 中有效地实现。一个典型的例子是两个 32 位带符号二进制补码整数的饱和加法，常用于 DSP 编程。以下示例显示了饱和加法运算的 C 实现
#include ;
int L_add(const int a, const int b)
{
    整数c;
    c = a + b; // 需要是 c = a + (无符号)b;以避免UB
    if (((a ^ b) & INT_MIN) == 0)
    {
        if ((c ^ a) & INT_MIN)
        {
            c=(a＜0)？ INT_MIN : INT_MAX;
        }
    }
    返回c；
}

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

From the ARM Website (ARM Info Center) on intrinsic functions:

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;
}

This example is unsafe in ISO C; signed integer overflow is undefined behaviour so you need to avoid causing it as part of detecting it. c = a + (unsigned)b; would avoid the problem, giving the expected binary integer result because 2's complement addition is the same as unsigned binary, but in C unsigned types have well-defined wrapping.

回复收藏 0 原文

~没有更多了~