带截断下溢的字符减法

Question

有没有办法计算：

/** clipped(a - b) **/
unsigned char clipped_substract(unsigned char a, unsigned char b)
{
    return a > b ? a - b : 0;
}

使用一些二元运算而不是测试？

Answer 1

/** clipped(a - b) **/
unsigned char clipped_substract(unsigned char a, unsigned char b)
{
    return a - (a+b) / 2 + getAbs(a-b) / 2;
}

unsigned int getAbs(int n)
{
    int const mask = n >> (sizeof(int) * 8 - 1);

    return ((n + mask) ^ mask);
}

Answer 2

原始函数编译为条件移动，不受您的性能问题的影响。您正试图在此处执行 premature optimization，这对您绝对没有好处。编写可读代码，然后分析它，然后识别和优化性能瓶颈。

你说"tests can lower performances"。如果你想像这样进行微优化，你应该着眼于理解这些经验法则背后的原因，而不是将它们作为无条件的真理来应用。

降低 "tests" 性能的是（错误预测的）控制流分支。现代 CPU 大量使用 instruction pipelining，控制流分支意味着不清楚接下来是哪条指令。常见的方法是 CPU 猜测（使用分支预测 hardware/algorithms）分支将走哪条路。如果弄错了，它必须冲洗整个管道并重新填充它，这会浪费周期。

嗯，有问题的代码没有这样的问题。它编译为条件移动：

https://godbolt.org/z/upkgok

clipped_substract(unsigned char, unsigned char):
    mov     eax, edi
    mov     edx, 0
    sub     eax, esi
    cmp     dil, sil
    cmovbe  eax, edx
    ret

可以看到这里没有控制流分支。请参阅 Why is a conditional move not vulnerable for Branch Prediction Failure? 了解为什么这不受上述性能问题的影响。

我重复一遍：编写可读代码，然后分析它，然后识别和优化性能瓶颈。您在这里尝试的是修复 的性能问题代码一开始甚至不存在（更不用说你没有证明这段代码的性能甚至与你的程序的性能相关）。

Answer 3

使用 clang 11.0，启用编译器优化

unsigned char clipped_substract(unsigned char a, unsigned char b)
{   
    long c = b - a;
    return ((unsigned long)c >> (sizeof(c)*8-1)) * c;
}

虽然任何替代方案所用的时间都可以忽略不计，但在执行 10000000 次迭代时，其他方法在我的机器上大约需要 0.300secs，而这个解决方案大约需要 0.200secs。

但这仅在您使用大小大于 char 的类型时有效，例如这里我使用 long。我不记得 char 或 long 的确切定义，但我知道 long 在我的机器上比 char 更宽。所以相应地调整它。

基本上，我只是将减法的结果存储在一个更大宽度的变量中。如果结果为负，最高有效位将是 1 否则 0.

带截断下溢的字符减法

Char substraction with clipped underflow

c

c++

binary-operators