转换为连续 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 在两个分支时可能具有的预期范围发生。

为此目的允许汇编机器代码。

编辑:

经过一番绞尽脑汁，我设法组装了一个可以工作的无分支版本:

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 值的范围(大概是分布)。不清楚他是否也意味着对你的值(value)。无论如何，享受我对他并没有真正提出的问题的改进答案]。

我认为您最好将其重新编码为:

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 生成器在每次调用时产生大量真正的随机位(例如 16)，您可以只调用一次(我假设 rand 比 divide 更昂贵，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;

如果您的编译器不会生成“正确”的指令，那么编写汇编代码应该很简单。