Ste*_* Lu 1 c c++ logic bit-manipulation
在从高性能代码中删除条件分支时,将真实布尔值转换unsigned long i = -1
为设置所有位可能很有用.
我想出了一种方法来从一个int b
(或bool b
)取值的输入获得这个整数掩码布尔值:1
或者0
:
unsigned long boolean_mask = -(!b);
Run Code Online (Sandbox Code Playgroud)
获得相反的价值:
unsigned long boolean_mask = -b;
Run Code Online (Sandbox Code Playgroud)
以前有人看过这个建筑吗?我有事吗?当int值-1(我假设-b
或-(!b)
确实产生)被提升为更大的unsigned int类型时,它是否保证设置所有位?
这是上下文:
uint64_t ffz_flipped = ~i&~(~i-1); // least sig bit unset
// only set our least unset bit if we are not pow2-1
i |= (ffz_flipped < i) ? ffz_flipped : 0;
Run Code Online (Sandbox Code Playgroud)
我会在下次问这样的问题之前检查生成的asm.听起来很可能编译器不会在这里给分支带来负担.
你应该问自己的问题是:如果你写:
int it_was_true = b > c;
Run Code Online (Sandbox Code Playgroud)
然后it_was_true
将是1或0. 但是那1来自哪里?
机器的指令集不包含以下形式的指令:
Compare R1 with R2 and store either 1 or 0 in R3
Run Code Online (Sandbox Code Playgroud)
或者,确实是这样的.(我在这个答案的最后给出了关于SSE的注释,说明前一个语句并不完全正确.)机器有一个内部条件寄存器,由几个条件位组成,还有比较指令 - 和其他一些算术运算 - 导致以特定方式修改这些条件位.随后,您可以根据某些条件位或条件加载执行条件分支,有时还可以执行其他条件运算.
实际上,将1存储在变量中的效率可能比直接完成某些条件运算要低得多.可能是,但也许不是,因为编译器(或者至少是编写编译器的人)可能比你更聪明,它可能只记得它应该放入1 it_was_true
以便当你实际到处时为了检查值,编译器可以发出适当的分支或其他.
所以,谈到聪明的编译器,你应该仔细看看由下面产生的汇编代码:
uint64_t ffz_flipped = ~i&~(~i-1);
Run Code Online (Sandbox Code Playgroud)
看一下这个表达式,我可以计算五个操作:三个按位否定,一个按位连接(and
)和一个减法.但是你不会在汇编输出中找到五个操作(至少,如果你使用gcc -O3).你会发现三个.
在我们查看汇编输出之前,让我们做一些基本的代数.这是最重要的身份:
-X == ~X + 1
Run Code Online (Sandbox Code Playgroud)
你能明白为什么会这样吗?-X
在2的补码中,只是另一种说法,即字中的位数.事实上,这就是为什么它被称为"2的补充".怎么样?好吧,我们可以把它当作从2的相应幂中减去X中的每一位的结果.例如,如果我们的单词中有四位,并且是(即5或2 2 + 2 0),然后是我们可以想到的,这是完全一样的.或者,换句话说:2n - X
n
~X
X
0101
~X
1010
23×(1-0) + 22×(1-1) + 21×(1-0) + 20×(1-1)
1111 − 0101
−X == 2n − X
~X == (2n−1) − X
意思就是
~X == (−X) − 1
记住,我们有
ffz_flipped = ~i&~(~i-1);
Run Code Online (Sandbox Code Playgroud)
但我们现在知道我们可以将〜(~i-1)改为minus
操作:
~(~i−1)
== −(~i−1) − 1
== −(−i - 1 - 1) − 1
== (i + 2) - 1
== i + 1
多么酷啊!我们本来可以写的:
ffz_flipped = ~i & (i + 1);
Run Code Online (Sandbox Code Playgroud)
这只是三个操作,而不是五个.
现在,我不知道你是否遵循了这一点,我花了一点时间才能做到正确,但现在让我们来看看gcc的输出:
leaq 1(%rdi), %rdx # rdx = rdi + 1
movq %rdi, %rax # rax = rdi
notq %rax # rax = ~rax
andq %rax, %rdx # rdx &= rax
Run Code Online (Sandbox Code Playgroud)
所以gcc只是自己想出了这一切.
关于SSE的承诺说明:事实证明,SSE可以进行并行比较,甚至可以在两个16字节寄存器之间进行16字节比较.条件寄存器不是为此而设计的,无论如何,没有人想要在不需要时进行分支.因此,CPU实际上将其中一个SSE寄存器(16字节的向量,或8"字"或4"双字",无论操作如何)更改为布尔指示符的向量.但它并不1
用于真实; 相反,它使用了所有1
s 的掩码.为什么?因为程序员可能会对该比较结果做下一件事就是使用它来掩盖值,我认为这正是你计划用你的-(!B)
技巧做的,除了并行流版本.
所以,请放心,它已被覆盖.