1

在从高性能代码中删除条件分支时，将真正的布尔值转换unsigned long i = -1为设置所有位可能很有用。

我想出了一种方法来从 a int b(or bool b) 的输入中获取这个 integer-mask-boolean ，取值1or 0：

unsigned long boolean_mask = -(!b);

要获得相反的值：

unsigned long boolean_mask = -b;

有人见过这种建筑吗？我在做某事吗？当 -1 的 int 值（我假设-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;

下次问这样的问题之前，我会检查生成的 asm。听起来编译器很可能不会在这里给 CPU 增加一个分支。

4

4 回答 4

5

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

int it_was_true = b > c;

那么it_was_true将是 1 或 0。但是那个 1 是从哪里来的呢？

机器的指令集不包含以下形式的指令：

Compare R1 with R2 and store either 1 or 0 in R3

或者，事实上，类似的东西。（我在这个答案的末尾写了一个关于 SSE 的注释，说明前一个陈述并不完全正确。）机器有一个内部条件寄存器，由几个条件位和比较指令 - 以及其他一些算术运算——导致以特定方式修改这些条件位。随后，您可以根据一些条件位或条件加载，有时还有其他条件操作，执行条件分支。

所以实际上，将 1 存储在变量中的效率可能比直接执行一些条件操作要低得多。可能是，但可能不是，因为编译器（或者至少是编写编译器的人）可能比你聪明，它可能只记得它应该把 1 放进去it_was_true，这样当你真正绕过时要检查该值，编译器可以发出适当的分支或其他任何东西。

所以，说到聪明的编译器，你应该仔细看看以下产生的汇编代码：

uint64_t ffz_flipped = ~i&~(~i-1);

看看那个表达式，我可以数出五个运算：三个按位否定、一个按位合取 ( and) 和一个减法。但是您不会在汇编输出中找到五个操作（至少，如果您使用 gcc -O3）。你会找到三个。

在我们查看汇编输出之前，让我们做一些基本的代数。这是最重要的身份：

-X == ~X + 1

你能明白为什么这是真的吗？-X，在 2 的补码中，只是另一种说法，其中是单词中的位数。事实上，这就是为什么它被称为“2 的补码”。怎么样？好吧，我们可以把它看作是从 2 的相应幂中减去 X 中的每一位的结果。例如，如果我们的字中有四位，并且是（即 5，或 2 2 + 2 0）， then是我们可以认为的，与 完全一样。或者，换句话说：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);

但是我们现在知道我们可以将 ~(~i−1) 变成minus运算：

~(~i−1)
== −(~i−1) − 1
== −(−i - 1 - 1) − 1
== (i + 2) - 1
== i + 1

多么酷啊！我们可以这样写：

ffz_flipped = ~i & (i + 1);

这只有三个操作，而不是五个。

现在，我不知道你是否遵循了这一点，我花了一些时间才把它弄好，但现在让我们看看 gcc 的输出：

    leaq    1(%rdi), %rdx     # rdx = rdi + 1 
    movq    %rdi, %rax        # rax = rdi                                        
    notq    %rax              # rax = ~rax                             
    andq    %rax, %rdx        # rdx &= rax

所以 gcc 只是自己解决了所有这些问题。

关于 SSE 的承诺说明：事实证明，SSE 可以进行并行比较，甚至可以在两个 16 字节寄存器之间一次进行 16 字节比较。条件寄存器不是为此而设计的，无论如何，没有人愿意在不需要时进行分支。因此，CPU 确实将其中一个 SSE 寄存器（一个 16 字节的向量，或 8 个“字”或 4 个“双字”，无论操作怎么说）更改为一个布尔指示符向量。但它并不1适用于真实；相反，它使用所有1s 的掩码。为什么？因为很可能程序员接下来对比较结果要做的事情就是用它来屏蔽值，我认为这正是你计划用你的-(!B)技巧做的事情，除了在并行流版本中。

所以，请放心，它已经被覆盖了。

于 2012-12-17T02:32:12.637 回答
1

有人见过这种建筑吗？我在做某事吗？

很多人都看过了。它像岩石一样古老。这并不罕见，但您应该将其封装在一个内联函数中以避免混淆您的代码。

并且，验证您的编译器实际上是在旧代码上生成分支，并且配置正确，并且这种微优化实际上提高了性能。（最好记下每个优化策略减少了多少时间。）

从好的方面来说，它完全符合标准。

当 -1 的 int 值（我假设 -b 或 -(!b) 确实产生）被提升为更大的 unsigned int 类型时，是否保证设置所有位？

请注意b尚未签名。由于无符号数始终为正数，因此强制转换的结果-1u并不特殊，也不会被更多的数扩展。

如果您有不同的尺寸并且想要肛门，请尝试以下操作：

template< typename uint >
uint mask_cast( bool f )
    { return static_cast< uint >( - ! f ); }
于 2012-12-17T01:16:07.380 回答
0 
struct full_mask {
  bool b;
  full_mask(bool b_):b(b_){}
  template<
    typename int_type,
    typename=typename std::enable_if<std::is_unsigned<int_type>::value>::type
  >
  operator int_type() const {
    return -b;
  }
};

利用：

unsigned long long_mask = full_mask(b);
unsigned char char_mask = full_mask(b);
char char_mask2 = full_mask(b); // does not compile

基本上我使用该类full_mask来推断我们要转换的类型，并自动生成该类型的位填充无符号值。我投入了一些 SFINAE 代码来检测我要转换的类型是无符号整数类型。

于 2012-12-17T01:57:13.943 回答
0

您可以通过递减将 1 / 0 转换为 0 / -1。这会反转布尔条件，但是如果您可以首先生成布尔值的倒数，或者使用掩码的倒数，那么它只是一个操作而不是两个。

于 2015-12-16T07:24:30.277 回答