将 x >= y 转换为 1 或 0，无需分支或布尔表达式

Question

我需要实现以下函数，无需分支或布尔表达式：

uint8_t func(uint32_t num, uint8_t shl)
{
    if (num >= (1 << shl))
    {
        return shl;
    }
    else
    {
        return 0;
    }
}

我做的第一步是注意到

else

部分很简单：

return num / (1 << shl);

当然，在

if

部分这样做并不一定会得到想要的结果。

所以我想我需要一些比

num / (1 << shl)

更“聪明”的东西。

如果我能想出一个可以给我

或

的表达方式，那么我就完成了。

是否有某种方法可以仅使用算术/位运算（即没有分支或布尔表达式）来做到这一点？

Answer 1

您可以将条件视为计算结果为 TRUE (1) 或 FALSE (0) 的布尔表达式，因此您可以使用如下所示的内容：

return (num >= (1 << shl)) * shl;

这段代码通常不是一个好主意，但在无分支约束下，它可以完成工作。

Answer 2

如果您想避免比较运算符，可以使用减法和位移位来探测符号位：

uint8_t func(uint32_t num, uint8_t shl) {
    return shl * (1 - ((num-(1<<shl)) >> (sizeof(num) * CHAR_BIT -1)));
}

Answer 3

假设您的实现执行算术移位（通常是这种情况）以及补码算术，您可以利用符号位传播：

uint8_t func(uint32_t num, uint8_t shl)
{
    return (-(int32_t)(num >> shl) >> 31) & shl;
}

这可能会转化为无分支 x86 汇编代码：

func(unsigned int, unsigned char):
  mov eax, edi
  mov ecx, esi
  shr eax, cl
  neg eax
  sar eax, 31
  and eax, esi
  ret

主要思想是

的左操作数要么全1，要么全零，这意味着

shl

的值要么被保留，要么被清零。

最棘手的部分是

-(int32_t)(num >> shl)

。它建立在事实之上：

Answer 4

那又怎样？

bool func( int32_t num, int8_t shl)
{
  return (num>=(1<<shl));
}