c++ - Bit hack 根据第二个值返回两个值之一

Question

假设 x是一个位掩码(即除 1 之外的所有位均为 0)并且 y是位掩码或等于 0。我需要一点技巧才能返回 x如果y非零，如果 y 则返回零为零。

这是一种可能的解决方案:取 x 的以 2 为底的对数和 y (使用 de Bruijn 序列)并减去它们，将值存储在 d 中.那么y << d将返回 x除非y一开始是零。

这种方法有两个问题:1) if y为零，从技术上讲，以 2 为底的对数是未定义的。不确定这是否重要，因为即使 d是一些垃圾值，y << d如果 y 仍应返回零为零； 2) 如果d是负数，右移运算符不会变成左移运算符(根据 Google 搜索)，这意味着我必须包括一些符号检查。

我相信有一种更简单的方法，但我找不到它，非常感谢您的帮助。

编辑:澄清一下，我正在寻找最快的方法来做到这一点。显而易见的if (y == 0) return 0; else return x使用 if语句，因此受到分支预测的不利影响，这就是为什么我要求助于复杂的 base-2 日志解决方案。

Answer 1

在大多数常见的处理器架构上，最好使用三元运算符:

/* if y != 0, return x, else return 0 */
int select1 (int x, int y)
{
    return y ? x : 0;
}

三元运算符的使用通常不涉及现代处理器架构上分支的使用，因为它可以通过使用条件移动(例如在 x86 上)、指令预测(例如在 ARM 上)或选择指令(例如在某些 GPU 上)。

如果不希望或不允许使用三元运算符，并且需要一种复杂的解决方案，则可以(假设平台对整数使用二进制补码表示)使用:

/* if y != 0, return x, else return 0 */
int select2 (int x, int y)
{
    return (0 - (y != 0)) & x;
}

请注意，select2() 可能比 select1() 慢。示例:如果我为 x86-64 架构编译上述函数，我的编译器会为 select1()

生成此指令序列

test      edx, edx
cmovne    edx, ecx
mov       eax, edx
ret

但是 select2() 的这个较长的指令序列:

mov       r8d, 1
test      edx, edx
cmovne    edx, r8d
neg       edx
and       edx, ecx
mov       eax, edx
ret

请注意，这两个指令序列都没有将分支作为值选择的一部分，但是与指令序列相比，select2() 中的指令序列需要执行更多的指令，并且具有更长的依赖链在 select1() 中。