是 - !(条件)从boolean(mask-boolean)获取全位向量的正确方法?

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.听起来很可能编译器不会在这里给分支带来负担.

ric*_*ici 5

你应该问自己的问题是:如果你写:

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 - Xn~XX0101~X101023×(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用于真实; 相反,它使用了所有1s 的掩码.为什么?因为程序员可能会对该比较结果做下一件事就是使用它来掩盖值,我认为这正是你计划用你的-(!B)技巧做的,除了并行流版本.

所以,请放心,它已被覆盖.