转换为无分支的连续if语句

Question

我在那里试图弄清楚如何将以下代码的最后两个"if"语句转换为无分支状态.

int u, x, y;
x = rand() % 100 - 50;
y = rand() % 100 - 50;

u = rand() % 4;
if ( y > x) u = 5;
if (-y > x) u = 4;

或者,如果上述情况太难,您可以将它们视为:

if (x > 0) u = 5;
if (y > 0) u = 4;

我认为让我感到困惑的是那些没有else接球手的事实.如果是这种情况,我可能已经适应了无分支abs(或max/ min)功能的变体.

rand()您看到的功能不是真实代码的一部分.我这样添加它们只是为了暗示变量的预期范围x,y并且u可能在两个分支发生时具有这些变量.

允许装配机器代码.

编辑:

经过一些braingrinding我设法组建一个工作无分支版本:

int u, x, y;
x = rand() % 100 - 50;
y = rand() % 100 - 50;

u = rand() % 4;
u += (4-u)*((unsigned int)(x+y) >> 31);
u += (5-u)*((unsigned int)(x-y) >> 31);

不幸的是,由于涉及整数运算,if语句的原始版本变得更快30%的范围.

编译器知道派对的位置.

Answer 1

[全部：这个答案是假设对 rand() 的调用是问题的一部分而编写的。我在这个假设下提出了下面的改进。OP 迟来地澄清他只使用 rand 来告诉我们 x 和 y 值的范围（以及大概的分布）。不清楚他是否也想为你带来价值。不管怎样，享受我对他没有真正提出的问题的改进答案]。

我认为你最好将其重新编码为：

int u, x, y;
x = rand() % 100 - 50;
y = rand() % 100 - 50;

if ( y > x) u = 5;
else if (-y > x) u = 4;
else u = rand() % 4;

这调用最后一个 rand 的频率仅为 OP 原始代码的 1/4。因为我假设 rand （和除法）比比较和分支昂贵得多，所以这将是一个巨大的节省。

如果你的 rand 生成器在每次调用时产生大量真正的随机位（例如 16），你可以只调用它一次（我假设 rand 比除法更昂贵，YMMV）：

int u, x, y, t;
t = rand() ;
u = t % 4;
t = t >> 2;
x = t % 100 - 50;
y = ( t / 100 ) %100 - 50;

if ( y > x) u = 5;
else if (-y > x) u = 4;

我认为如果你想要真正的随机值，MS C 库中的 rand 函数对此还不够好。我必须自己编写代码；无论如何，结果更快。

您还可以通过使用倒数相乘（未经测试）来消除除法：

int u, x, y;
unsigned int t;
unsigned long t2;
t = rand() ;
u = t % 4;

{ // Compute value of x * 2^32 in a long by multiplying.
  // The (unsigned int) term below should be folded into a single constant at compile time.
  // The remaining multiply can be done by one machine instruction
  // (typically 32bits * 32bits --> 64bits) widely found in processors.
  // The "4" has the same effect as the t = t >> 2 in the previous version
  t2 = ( t * ((unsigned int)1./(4.*100.)*(1<<32));
}
x = (t2>>32)-50; // take the upper word (if compiler won't, do this in assembler)
{ // compute y from the fractional remainder of the above multiply,
  // which is sitting in the lower 32 bits of the t2 product
  y = ( t2 mod (1<<32) ) * (unsigned int)(100.*(1<<32));
}

if ( y > x) u = 5;
else if (-y > x) u = 4;

如果您的编译器不能生成“正确”的指令，那么编写汇编代码来执行此操作应该很简单。