在C语言中进行带符号饱和乘2的运算，需要6个操作。

Question

在C语言中进行带符号饱和乘2的运算，需要6个操作。

cbit-manipulationbitwise-operatorsmicro-optimizationsaturation-arithmetic

6

对于32位带符号的二进制补码整数存在以下问题:

satMul2 - 将输入数乘以2，如果溢出则饱和至Tmin或Tmax。
示例: satMul2(0x30000000) = 0x60000000
satMul2(0x40000000) = 0x7FFFFFFF (饱和至TMax)
satMul2(0x60000000) = 0x80000000 (饱和至TMin)
合法操作: ! ~ & ^ | + << >>
最大操作数: 20
评分: 3

我想要实现一个类似的函数。

if (a) return b;
else return c;

这是我的解决方案（10次操作）：

int satMul2(int x) {
    int rval = x << 1;
    int sign = rval ^ x;
    int minn = 1 << 31;
    int temp = sign >> 31;
    int flow = minn ^ (rval >> 31);
    return ((~temp) & rval) | (temp & flow);    
}

我的教授告诉我有一种解决方案只需要6个操作。请问有人可以给我一些提示吗？

- Mint

1

使用您的实现，satMul2(0x60000000) 对我而言返回的是 0x7FFFFFFF 而不是 0x80000000。在所有溢出情况下，返回 Tmin 或 Tmax 是否有条件限制，或者两者都可以吗？ - Nelfeal

@Nelfeal：我认为这只是一个示例中的错误，并且结果应该始终与输入具有相同的符号，就像 Rust 的 i32.saturating_mul乘以2一样，或者 x.saturating_add(x)。（https://godbolt.org/z/4646v7noP 显示了rustc在 x86-64 上的实现）。 0x60000000 没有设置它的 MSB（最高位十六进制数字<8），因此它表示非负的有符号整数值。 - Peter Cordes

1

((~temp) & rval) | (temp & flow) ⇔ ((flow ^ rval) & temp) ^ rval。 - njuffa

4个回答

3

使用超级优化器，我已经找到了一种方法，只使用6个操作，假设我们有一个算术移位，它进行符号扩展并仅查看移位计数的低5位（就像大多数当前的CPU一样）。

int my_satmul2(int x) {
    unsigned r1 = (unsigned)x + 0x40000000;
    unsigned r2 = (int)r1 >> 31;
    unsigned r3 = r1 + r1;
    unsigned r4 = (int)r3 >> (r2 & 31);
    unsigned r5 = r4 + 0x80000000;
    unsigned r6 = r5 ^ r2;
    return r6;
}

当值需要饱和时，r1 为负，r2 全部设置为1。当 x 为负时，r3 为负，r4 是相应的全为1或全为0的掩码。对于 r5，我们切换最高位，对于 r6，我们取反，得到 0x80000000 （INT_MIN），0x7fffffff （INT_MAX）。

当值不需要饱和时，r1 为正，r2 全部设置为0。在 r3 中，我们有 2*x + 0x80000000，这已经是翻转了最高位的正确结果。这在 r5 中得到修复，而 r4 和 r6 则不起作用。

编辑： 这里有另一种不需要大常数的变体。

int my_satmul2(int x) {
    unsigned r1 = ((unsigned)x) << 1;     // 2x
    unsigned r2 = r1 ^ x;                 // high bit: 1 iff saturation needed
    unsigned r3 = ((int)r2) >> 31;        // all-1 iff saturating, 0 otherwise
    unsigned r4 = r3 << (r3 & 31);        // 0x80000000 if saturating, 0 otherwise
    unsigned r5 = ((int)r1) >> (r3 & 31); // 2x if not saturating, otherwise all-0
                                          // or all-1 depending on direction
    unsigned r6 = r4 ^ r5;                // 2x if not saturating,
                                          // otherwise 0x80000000 or ~0x80000000
    return r6;
}

- Falk Hüffner

哇，现在我真的想知道教授是否考虑到这一点，或者是否有更简单的方法，例如不涉及变量计数移位0或1（符号位或早期结果）。很酷的发现，感谢您发布这个。 - Peter Cordes

很好。依照我的理解，规则是常量例如 0x40000000 和 0x80000000 必须通过移位生成，即视为一次操作（请参见问题代码中的 int minn = 1 << 31;）。值得一提的是，在godbolt上尝试多个工具链/架构，我无法将上述代码编译成少于7条指令。 - njuffa

1

更正：在编译器资源网站Compiler Explorer (godbolt.org)上，x86-64 icc 2021.6.0确实将上述代码编译为六个指令序列。 - njuffa

我已经添加了一个版本，它使用六个指令，同时只使用移位计数作为常量。 - Falk Hüffner

1

除非satMul2()的功能、可用操作或操作计数与问题陈述不同，否则我认为在六个操作内无解。

如果需要直接易懂的实现，请参考chqrlie的答案。如果我们坚持使用位运算实现，则需要在中间计算中使用unsigned int以保证可移植性。在有符号整数加法中，只有当两个加数具有相同的符号且结果的符号与两个源操作数的符号不同时，才会发生溢出。在补码运算中，我们假设这里的情况是这样的，在溢出情况下，夹紧边界可以根据源操作数的符号或原始加法结果的符号来确定，因为在这种情况下，所需的夹紧边界与它们相反。

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

unsigned int my_satmul2 (unsigned int a)
{
    const int max_shift = CHAR_BIT * sizeof (a) - 1;
    const unsigned int msb = 1u << max_shift;
    unsigned int r, bound;
    r = a + a;
    bound = (0 - (r >> max_shift)) + msb; // alternative: msb - 1 + (a >> max_shift)
    r = ((r ^ a) & msb) ? bound : r;
    return r;
}

int satMul2(int x) {
    return x > INT_MAX / 2 ? INT_MAX :
           x < INT_MIN / 2 ? INT_MIN : x * 2;
}

int main (void)
{
    unsigned int a, res, ref;

    a = 0;
    do {
        ref = satMul2 (a);
        res = my_satmul2 (a);
        if (res != ref) {
            printf ("a=%08x res=%08x ref=%08x\n", a, res, ref);
            return EXIT_FAILURE;
        }
        a++;
    } while (a);
    return EXIT_SUCCESS;
}

在编译器浏览器上检查生成的代码，我们发现针对x86-64架构的clang 15.0.0生成了非常高效的代码:

my_satmul2:
        lea     ecx, [rdi + rdi]
        mov     eax, ecx
        sar     eax, 31
        add     eax, -2147483648
        xor     edi, ecx
        cmovns  eax, ecx
        ret

针对x86-64架构，gcc 12.2生成的代码同样高效，但略有不同：

my_satmul2:
        lea     eax, [rdi+rdi]
        cdq
        add     edx, -2147483648
        xor     edi, eax
        cmovs   eax, edx
        ret

由于本题不允许使用三目运算符，需要利用全0或全1掩码的复用结构进行替换。此外，减法也是不允许的，因此a-b必须被替换为a+~b。

unsigned int my_satmul2 (unsigned int a)
{
    const int max_shift = CHAR_BIT * sizeof (a) - 1;
    const unsigned int msb = 1u << max_shift;
    unsigned int r, bound, omask;
    r = a + a;
    omask = 1 + ~((a ^ r) >> max_shift);
    bound = msb + ~(r >> max_shift) + 1;
    r = ((bound ^ r) & omask) ^ r;
    return r;
}

在创建了上述代码之后，与提问者的算法相比，我发现它基本上使用了相同的算法，但依赖于有符号整数的右移会转换为算术右移指令这一事实，而C标准并不保证：“E1 >> E2 的结果是 E1 右移 E2 位...如果 E1 具有带符号类型和负值，则生成的值是实现定义的。”

有趣的是，针对x86-64架构，clang 15.0.0生成的代码与使用三元运算符的简单版本完全相同！而gcc 12.2在x86-64上表现不太好：

my_satmul2:
        lea     edx, [rdi+rdi]
        mov     eax, edx
        xor     edi, edx
        sar     eax, 31
        sar     edi, 31
        add     eax, -2147483648
        xor     eax, edx
        and     eax, edi
        xor     eax, edx
        ret

- njuffa

1

带符号饱和位运算技巧

注意饱和返回值（0x7FFFFFFF 和 0x80000000）是彼此按位取反的，我们可以通过 tmp ^ 0x7FFFFFFF 生成它们，其中 tmp = x>>31，根据符号为全零或全一。还可以使用((unsigned)x>>31) + (unsigned)INT_MAX，0x7FFFFFFFu + (0 or 1)。（使用无符号来避免C中的有符号溢出UB）

这就是 Rust 所做的，对于 x.saturating_mul(2) 或 x.saturating_add(x)。（没错，Rust 在所有原始整数类型上都有饱和加法和乘法作为基本操作。如果你使用 Rust，你会把这算作一个“操作”吗？CPU 不运行源代码，它们运行汇编语言。有些语言的操作比大多数 CPU 更受限制，特别是 C 语言，它也缺少旋转、popcount、clz/ctz；C++ 直到 C++20 才通过 #include <bit> 添加了这些功能。）

// Rust
pub fn saturating_mul2(x: i32) -> i32 {
    x.saturating_mul(2)
}

pub fn saturating_add_self(x: i32) -> i32 {
    x.saturating_add(x)
}

使用x86-64、AArch64和--target armv7-unknown-linux-gnueabi的汇编代码，请参见Godbolt：

example::saturating_mul2:           @@ ARMv7
        adds    r1, r0, r0               @ add, updating flags (S suffix)
        mvn     r2, #-2147483648         @ r2 = ~0x80000000 = 0x7FFFFFFF
        eorvs   r1, r2, r0, asr #31      @ if (adds overflowed) r1 = 0x7FFFFFFF ^ (x>>31);
                 @ eorvs is predicated on V Set = signed overflow, otherwise r1 left unmodified holding x+x
        mov     r0, r1                @ get the result into the same reg as the input
        bx      lr

example::saturating_add_self:
        qadd    r0, r0, r0          @ yup, ARMv7 has an instruction for this!
        bx      lr                  @ the mul(2) version is a missed optimization

或者使用AArch64：

example::saturating_mul2:
        asr     w8, w0, #31
        adds    w9, w0, w0                // x+x and set flags
        eor     w8, w8, #0x7fffffff
        csel    w0, w8, w9, vs            // select 
        ret

example::saturating_add_self:
        adds    w8, w0, w0             // x+x and set flags
        asr     w9, w8, #31            // (x<<1)>>31 is the opposite of the sign of the correct result, if there was overflow
        eor     w9, w9, #0x80000000
        csel    w0, w9, w8, vs
        ret

请注意，LLVM的add_self版本策略类似于一般的x+y饱和运算。它使用与adds相反的符号来表示x+x结果，因此它具有更差的延迟和指令级并行性（右移必须等待add完成，而不能在同一输入上分别运行）。如果实际结果与数学上正确的结果有不同的符号，则有符号溢出。因此，如果您有两个可能具有不同符号的单独输入，这是一个好的技巧。但实际上这并不是必要的：只有当两个输入具有相同的符号时，+才会溢出，因此您可以选择任何一个输入。

x86-64版本与AArch64版本非常相似，但需要额外的mov指令。（或者使用.saturating_add版本，使用lea进行一次+运算以提供sar右移操作的输入，再使用add生成潜在的返回值并设置OF标志以进行cmov操作。）

有一个可选的/建议的C扩展，其中包含_Sat类型；请参见SO答案，以及使用它进行加法的示例：https://godbolt.org/z/5EdP1EnxT。

如何让C编译器生成这样的汇编代码？

将饱和结果生成为(x>>31) ^ 0x7FFFFFFF非常容易。至少如果您可以假设>>是算术右移的话。对于有符号负整数的>>是实现定义行为，但所有主流编译器都选择以有用的方式定义它，至少在2补码系统上。

因此，只是需要以某种方式检测左移中的有符号溢出。

不幸的是，在ISO C中，有符号整数溢出是未定义行为，包括在x << 1中。GNU C定义了即使移位溢出也会发生的行为（与x+x不同，您必须使用__builtin_sadd_overflow），所以我不知道您关心的可移植性有多高。

如果您愿意使用GNU C溢出检测内置函数（通常可以编译成使用由加法设置的溢出标志，因此这确实是一种原始机器操作），请参见Signed saturated add of 64-bit ints? - 对于AArch64，clang会发出4条指令，与rustc的饱和数学相当，尽管使用add x9，x9，x1，lsr #63来执行INT64_MAX+0或1。 如果您只关心二进制补码机器，可以在C源代码中使用无符号类型进行左移。整个位运算基本上已经假定了这一点，因此我们只需要对比较0使用有符号类型，或者进行算术右移。

#include <stdint.h>
// int32_t is guaranteed to be 2's complement with exactly 32 value bits, if it exists
// >> on it is *not* guaranteed to be arithmetic, but we can fairly safely assume that
int saturating_shl (int32_t x)
{
    int32_t saturated = (x>>31) ^ 0x7FFFFFFF;   // 2 operations, plus maybe a MOV
    int32_t x2 = ((uint32_t)x) << 1;            // 1 op.  avoid signed-integer overflow
    int32_t overflow = (x ^ x2);             // 1 op.  negative if x and x*2 have different signs, i.e. overflow
    return  (overflow < 0) ? saturated : x2;  // 1 op (cmov)
}

这是次优的；编译器未能使用ALU加法或左移指令的有符号溢出结果，而实际上是与原始值进行异或运算。但它仍然只有源代码中的5个操作，例如x86-64的GCC（Godbolt）。

saturating_shl:
        mov     edx, edi
        lea     eax, [rdi+rdi]       # x<<1
        sar     edx, 31              # x>>31
        xor     edx, 2147483647      # saturated
        xor     edi, eax             # x ^ x2 to set FLAGS
        cmovs   eax, edx             # SF is set when (x^x2) < 0
        ret

更新：我错过了问题任意禁用三元运算符的部分。我不会再进行编辑，因为@njuffa发布了一个避免它的答案，使用clang编译到与三元版本相同的指令。（虽然在GCC中生成更糟糕的汇编代码，它无法将混合惯用语排序回cmov / csel。）

计算操作 - CPU汇编语言，而非C运算符

真正的CPU运行机器码，而不是C运算符。在微观优化时，重要的是您的代码在特定的机器上能够高效地编译。现代机器通常具有条件选择指令，例如x86的cmov或AArch64的csel，因此像((~temp) & rval) | (temp & flow);这样手动根据掩码进行混合的表达式可以希望编译为一个机器操作，使用FLAGS条件而不是从中生成整数掩码。

如果这是使用SIMD自动向量化，那么SIMD比较已经产生了一个所有0或所有1元素的掩码，许多指令集都有混合指令可以应用它们，例如x86的SSE4.1的。此外，许多指令集还有像x86的SSE2的andnot指令，它可以在单个指令中执行(~mask) & rval，因此混合需要3个廉价指令，而不是一个更少廉价的pblendvb，它在某些CPU上需要2个微操作；参见https://uops.info/。

但另一方面，在像x86这样没有AVX只能执行z = x; z &= y;而不能在单个指令中执行z = x&y的机器上，额外的寄存器-寄存器mov或movdqa指令也是您需要担心的成本的一部分。

TL:DR：在C语言中计算运算符的数量可能是成本的一个粗略代理，但并不是精确的。除了吞吐量之外，还有其他考虑因素，例如延迟（从输入到输出的关键路径长度）和指令级并行性。某些机器具有可以执行C语言没有单个运算符的指令。例如，32位ARM具有饱和带符号加法qadd，因此如果编写正确且编译器识别您正在使用的“惯用法”，则足够聪明的编译器可以将您的函数优化为一个指令。实际上，编译器可以为一些事情做到这一点，例如使用(x >> (n&31)) | (x << ((-n)&31))进行旋转编译为x86 rol。许多真正的CPU基于有符号溢出或MSB设置FLAGS，因此比起右移并使用掩码，比较和三元操作有时对编译器来说更容易解决。