一尘不染

如何在C中进行无符号饱和加法?

algorithm

用C编写饱和加法的最佳(最简洁,最有效)方法是什么?

函数或宏应添加两个无符号输入(需要16位和32位版本),如果总和溢出,则返回全1(0xFFFF或0xFFFFFFFF)。

目标是使用gcc(4.1.2)和Visual Studio的x86和ARM(仅用于模拟,因此可以进行后备实现)。


阅读 326

收藏
2020-07-28

共1个答案

一尘不染

您可能C在这里需要可移植的代码,您的编译器会将这些代码转换为正确的ARM汇编。ARM有条件移动,而这些可能是有条件溢出的。然后,该算法将成为add,并在检测到溢出时有条件地将目标设置为unsigned(-1)。

uint16_t add16(uint16_t a, uint16_t b)
{
  uint16_t c = a + b;
  if (c<a) /* Can only happen due to overflow */
    c = -1;
  return c;
}

请注意,这与其他算法的不同之处在于它可以纠正溢出,而不是依靠其他计算来检测溢出。

用于add32的x86-64 clang 3.7
-O3输出
:明显优于其他任何答案:

    add     edi, esi
    mov     eax, -1
    cmovae  eax, edi
    ret

ARMv7:gcc 4.8 -O3 -mcpu=cortex-a15 -fverbose- asmadds32的输出

    adds    r0, r0, r1      @ c, a, b
    it      cs
    movcs   r0, #-1         @ conditional-move
    bx      lr

16位:仍不使用ARM的无符号饱和加法指令(UADD16

    add     r1, r1, r0        @ tmp114, a
    movw    r3, #65535      @ tmp116,
    uxth    r1, r1  @ c, tmp114
    cmp     r0, r1    @ a, c
    ite     ls        @
    movls   r0, r1        @,, c
    movhi   r0, r3        @,, tmp116
    bx      lr  @
2020-07-28