"Moving"数字朝向另一个数字而不超过它 - 任何无分支版本？

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可以向target取一个完整的step，所以我们想要value - step
• 如果CCD_ 17<CCD_ 18<value + step，那么value不能将完整的step带向target(可能在任一方向(，所以我们想要target
• 如果CCD_ 24<value + step≤target，那么value可以向target取一个完整的step，所以我们想要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

我认为这就是Francois Andrieux所暗示的方法。你试过这个吗？这只是一个分支。

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++。