有没有一种无分支的方式可以将号码移动到另一个号码而不超过它？

Question

我想实现一个符合以下接口和契约的功能：

void move_towards(float& value, float target, float step) 
    // Moves `value` towards `target` by `step`. 
    // `value` will never go beyond `target`, but can match it.
    // If `step == 0.0f`, `value` is unchanged.
    // If `step > 0.0f`, `std::abs(target - value)` decreases.
    // If `step < 0.0f`, the behavior is undefined.

这个想法是使用此函数逐渐将现有浮点值移向另一个浮点值，而不会超过目标。这很有用，例如，作为游戏循环执行的一部分，在值之间执行线性转换。

这是一个示例测试用例：

float value = 5.0f;
move_towards(value,  10.f,  1.f); assert(value ==  6.0f);
move_towards(value,  10.f,  1.f); assert(value ==  7.0f);
move_towards(value, -5.f,   5.f); assert(value ==  2.0f);
move_towards(value, -5.f,   5.f); assert(value == -3.0f);
move_towards(value, -5.f,   5.f); assert(value == -5.0f);
move_towards(value, -5.f,   5.f); assert(value == -5.0f);
move_towards(value,  0.f,  15.f); assert(value ==  0.0f);

我使用

std::copysign

和

std::clamp

的组合尝试了一些无分支的想法，但它们在某些边缘情况下总是失败。最后，我求助于使用分支版本：

void move_towards(float& value, float target, float step) 
{
    if (value < target)
    {
        value += step;
        if (value > target)
        {
            value = target;
        }
    }
    else if (value > target)
    {
        value -= step;
        if (value < target)
        {
            value = target;
        }
    }
}

在 godbolt.org 上直播

• 是否可以实现

  move_towards

  以生成无分支指令？
• 如果没有，是否可以至少最小化分支数量？
• 无论如何，哪个版本提供最佳的运行时性能？

Answer 1

期望的结果是

value - step

、

value + step

和

target

的中位数，所以这样可以：

void move_towards(float &value, float target, float step) 
{
    value = std::max(value - step, std::min(value + step, target));
}

要看到这一点，请考虑

target

位于

value - step

和

value + step

下方、之间或上方的情况：

• 如果

  target

  ≤

  value - step

  <

  value + step

  ，那么

  value

  可以向

  step

  向下移动一个完整的

  target

  ，所以我们想要

  value - step

  。
• 如果

  value - step

  <

  target

  <

  value + step

  ，那么

  value

  不能将完整的

  step

  朝向

  target

  （可能在任一方向），所以我们想要

  target

  。
• 如果

  value - step

  <

  value + step

  ≤

  target

  ，那么

  value

  可以向

  step

  方向移动一个完整的

  target

  ，所以我们想要

  value + step

  。

在每种情况下，我们都想要中间值。

测试显示，如果我们交换

std::max

操作数，GCC 会生成更少的两条指令，可能只是因为它与操作数恰好位于寄存器中的位置配合得更好：

void move_towards(float &value, float target, float step) 
{
    value = std::max(std::min(value + step, target), value - step);
}

Answer 2

我认为这就是弗朗索瓦·安德烈所暗示的方法。 你试过这个吗？这只是一根树枝。

void move_towards(float& value, float target, float step) {
    value = target < value 
        ? std::max(value - step, target)
        : std::min(value + step, target);
}

https://godbolt.org/z/jxKP6oT1h

Answer 3

如果您有一个相当现代的处理器目标（从两个浮点值进行无分支选择），则可以完全无分支地执行此操作。

该方法是将问题表述如下：

计算“有符号步长”值，该值是

+step

或

-step

，具体取决于

target > value

或

target < value

。求

target

、

value

和

value + signed step

的中位数。找到中位数可以通过排序来完成，但是对于三个元素，您也可以仅通过可逆运算将元素组合起来，并对三个值中的最大值和最小值的组合应用逆运算。对于

float

，可逆运算有点问题，因为加法/减法不具有关联性。然而，在您的评论中，您说您不关心目标和值具有极大不同大小的情况，因此加法和减法工作得很好。更好的解决方案是按位转换为相同宽度的无符号整数类型，然后使用

xor

作为可逆运算，然后将中位数位模式转换回浮点数。

这是godbolt的解决方案，答案是：

void move_towards(float& value, float target, float step) {
    auto sstep = (target > value ? step : -step);
    auto nval = value + sstep;
    value = value + target + nval -
        std::min(std::min(value, target), nval) -
        std::max(std::max(value, target), nval);
}

Answer 4

有无分支版本吗？

使用

target - value

符号按索引选择功能。

float move_towards(float value, float target, float step) {
  static float (*f[2])(float a, float b) = {fminf, fmaxf};
  float diff = target - value;
  bool index = signbit(diff);
  step = copysignf(step, 0 - index);
  return f[index](target, value + step);
}

代码是C 解决方案。留给 OP 根据需要翻译成 C++。