假设x
是位掩码(即除一位外,其所有位都为0),y
是位掩码或等于0。如果y
为非零,我需要一个比特破解来返回x
,如果y
为零,则返回零。
这里有一个可能的解决方案:取x
和y
的以2为底的对数(使用德布鲁因序列)并将其相减,将值存储在d
中。则y << d
将返回x
,除非y
一开始为零。
这种方法有两个问题:1)如果y
为零,那么从技术上讲,以2为底的对数是未定义的。但不确定这是否重要,因为即使d
是某个垃圾值,如果y
为零,y << d
也应该返回零;2) 如果d
为负,则右移运算符不会变成左移运算符(根据谷歌搜索),这意味着我必须包括一些符号检查。
我相信有一种更简单的方法,但我找不到,希望能得到一些帮助。
编辑:为了澄清,我正在寻找最快的方法。显而易见的if (y == 0) return 0; else return x
使用了if
语句,因此受到分支预测的不利影响,这就是为什么我要使用复杂的base-2 log解决方案。
在大多数常见的处理器架构上,使用三元运算符是首选:
/* 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
但是CCD_ 22:的这个较长的指令序列
mov r8d, 1
test edx, edx
cmovne edx, r8d
neg edx
and edx, ecx
mov eax, edx
ret
请注意,两个指令序列都不涉及作为值选择的一部分的分支,但与select1()
中的指令序列相比,select2()
中的指令顺序需要执行更多的指令,并且具有更长的依赖链。
static_cast<bool>(y) * x
只需取y,并使用其位形成一个所有1的字符串,如果它为非零,则将其与x进行and运算。实现这一点的愚蠢方法是线性的,但也可以使用二进制方法(未给出)。
#include <stdio.h>
#include <limits.h>
int foo(int x, int y) {
int z = 0;
for(int z = 1; z < CHAR_BIT * sizeof(int); z ++) {
y |= y << z;
}
return x & y;
}
int main() {
printf("%lxn", foo(0x1000, 0xdead));
return 0;
}
这应该在恒定的时间内运行。你当然可以展开这个循环。