可以在单个 CPU 指令中在 0 和 1 之间翻转 bit/integer/bool 的任何可能代码

Question

单个 x86 指令能否在“0”和“1”之间切换布尔值？

我想到了以下方法，但都导致了两条带有 gcc 的 -O3 标志的指令。

status =! status;

status = 1 - status;

status  = status == 0 ? 1: 0;

int flip[2] = {1, 0};
status = flip[status];

有更快的方法吗？

这是我试过的：https://godbolt.org/g/A3qNUw

我需要的是一个可以切换输入和 returns 的函数，该函数以编译为一条指令的方式编写。类似于此功能的内容：

int addOne(int n) { return n+1; }

compiles on Godbolt 到此:

  lea eax, [rdi+1]    # return n+1 in a single instruction
  ret

Answer 1

从这个code run of Godbolt（这段代码基本上包含我尝试过的几个选项）看来 XORing 给出了一个可以做到这一点的语句：-（正如你所说的切换是你正在寻找的）

status ^= 1;

归结为只有一条指令（这是 -O0）

xor DWORD PTR [rbp-4], 1

使用 -O3 你可以看到你提到的所有方法都使用 xor 并且这个特别是 mov eax, edi/xor eax, 1.

这确保状态在 0 和 1 之间来回切换，反之亦然。（因为有 xor 语句——在大多数架构中都有，在很多情况下都很有用）。

我让另一个内存访问选项落空了 - 因为指针算法和取消引用地址不会比这些更快（有可能的内存访问）。

我建议了一种基于 Godbolt 中的小混乱的方法。你可以从这里做的是 - 比较不同的做法，然后得到你得到的时间结果。据推测，您将获得的结果 XOR-ing 在您的机器架构上不会那么糟糕。

有趣的是，示例中的 Peter Cordes showed 这也适用于布尔值。

有了这个 example 很明显，编译器优化了未优化代码与 1 版本的异或运算。这是支持异或运算在正常 int 操作的情况下会产生更好结果这一事实的一种方式。使用 -O3 编译时使用布尔值，上面显示的所有值都会滴入 mov eax, edi/xor eax, 1.

Answer 2

要翻转整数中的位，请像这样使用 xor：foo ^= 1.

gcc 已经知道 bool 的这种优化，因此您可以像正常人一样 return !status; 而不会损失任何效率。 gcc 也将 status ^= 1 编译为 xor 指令。事实上，除了 table 查找之外，您的所有想法都编译为具有 bool 输入/ return 值的单个 xor 指令。

检查 on the Godbolt compiler explorer 和 gcc -O3，以及 bool 和 int 的 asm 输出窗格。

MYTYPE func4(MYTYPE status) {
    status ^=1;
    return status;
}

  # same code for bool or int
  mov eax, edi
  xor eax, 1
  ret

对比

MYTYPE func1(MYTYPE status) {
    status = !status;
    return status;
}

  # with -DMYTYPE=bool
  mov eax, edi
  xor eax, 1
  ret

  # with int
  xor eax, eax
  test edi, edi
  sete al
  ret

为什么 `bool` 与 `int` 不同？

The x86-64 System V ABI 要求传递 bool 的调用者传递 0 或 1 值，而不仅仅是任何 non-zero 整数。因此，编译器可以假设输入。

但是对于 int foo，C 表达式 !foo 需要 "booleanizing" 值。 !foo 的类型为 _Bool /（如果您 #include <stdbool.h> 则又称为 bool），并且将其转换回整数必须产生 0 或 1 的值。如果编译器不不知道foo一定是0或1，无法将!foo优化为foo^=1，也无法实现foo ^= 1在 truthy / falsy 之间翻转一个值。（在某种意义上，if(foo) 在 C 中表示 if(foo != 0)）。

这就是为什么在test之前得到test/setcc（zero-extended变成32位int）。

相关：。 (bool1 && bool2) ? x : y 之类的东西并不总是像您希望的那样高效地编译。编译器非常好，但确实有 missed-optimization 个错误。

那个额外的 `mov` 指令呢？

如果编译器不需要/不想保留旧的 un-flipped 值以备后用，内联时它将消失。但是在 stand-alone 函数中，第一个参数在 edi 中，而 return 值需要在 eax 中（在 x86-64 System V 调用约定中）。

像这样的小函数非常接近作为大型函数的一部分可能得到的函数（如果不能将此翻转优化为其他函数），但需要将结果保存在不同的寄存器中是一个混杂因素.

x86 没有 copy-and-xor 整数指令 ，因此对于 stand-alone 函数，至少需要 mov从 arg-passing 寄存器复制到 eax.

lea 是特殊的：它是为数不多的整数 ALU 指令之一，可以将结果写入不同的寄存器而不是破坏其输入。 lea 是，但 x86 中没有 copy-and-xor 指令。许多 RISC 指令集有 3 个操作数指令，例如 MIPS 可以做到 xor $t1, $t2, $t3.

AVX 引入了 non-destructive 版本的矢量指令（在很多代码中节省了很多 movdqa / movups register-copying），但是对于整数只有一些做不同事情的新指令。 rorx eax, ecx, 16 例如 eax = rotate_right(ecx, 16)，并使用 non-destructive AVX 指令使用的相同 VEX 编码。

Answer 3

如果您尝试 micro-optimize 布尔运算，您要么过早优化，要么对大量布尔数据进行大量运算。对于前者——答案是否定的；对于后者，您可能问错了问题。如果真正的问题是如何优化（许多）布尔数据的（许多）操作，答案是使用基于 "flags" 的替代表示（a.k.a。使用更好的算法）。这将使您能够以可移植和可读的方式将更多数据放入缓存并同时执行多个操作和测试。

Why/How这样更好吗？

缓存

考虑一个缓存行大小为 64 字节的系统。 64 _Bool 将适合数据缓存行，而该数量的 8 倍将适合。您可能还会有更小的指令代码——从 1 条额外指令到减少 32 倍不等。这可以在紧密循环中产生很大的不同。

运营

大多数操作涉及一个或两个（通常非常快）操作和一个测试，无论您要测试多少标志。由于这可以同时包含多个值，因此每个操作可以完成（通常是 32 或 64 倍）更多的工作。

分支

由于可以同时完成多个操作和测试，因此可以将最多32（或64）个可能的分支减少为一个。这可以减少分支预测错误。

可读性

通过使用命名良好的掩码常量，可以将复杂的嵌套 if-else-if-else 块简化为单个可读行。

便携性

_Bool 在 C 的早期版本中不可用，C++ 使用不同的布尔机制；但是，flags 将在旧版本的 C 中工作并且与 C++ 兼容

下面是一个如何设置带标志的掩码的实际示例：

int isconsonant(int c){
    const unsigned consonant_mask = (1<<('b'-'a'))|
    (1<<('c'-'a'))|(1<<('d'-'a'))|(1<<('f'-'a'))|(1<<('g'-'a'))|
    (1<<('h'-'a'))|(1<<('j'-'a'))|(1<<('k'-'a'))|(1<<('l'-'a'))|
    (1<<('m'-'a'))|(1<<('n'-'a'))|(1<<('p'-'a'))|(1<<('q'-'a'))|
    (1<<('r'-'a'))|(1<<('s'-'a'))|(1<<('t'-'a'))|(1<<('v'-'a'))|
    (1<<('w'-'a'))|(1<<('x'-'a'))|(1<<('y'-'a'))|(1<<('z'-'a'));
    unsigned x = (c|32)-'a'; // ~ tolower
    /* if 1<<x is in range of int32 set mask to position relative to `a`
     * as in the mask above otherwise it is set to 0 */
    int ret = (x<32)<<(x&31);
    return ret & consonant_mask;
}
//compiles to 7 operations to check for 52 different values
isconsonant:
  or edi, 32 # tmp95,
  xor eax, eax # tmp97
  lea ecx, [rdi-97] # x,
  cmp ecx, 31 # x,
  setbe al #, tmp97
  sal eax, cl # ret, x
  and eax, 66043630 # tmp96,
  ret

这个概念可用于同时对模拟的布尔值数组进行操作，例如：

//inline these if your compiler doesn't automatically
_Bool isSpecificMaskSet(uint32_t x, uint32_t m){
    return x==m; //returns 1 if all bits in m are exactly the same as x
}

_Bool isLimitedMaskSet(uint32_t x, uint32_t m, uint32_t v){
    return (x&m) == v;
    //returns 1 if all bits set in v are set in x
    //bits not set in m are ignored
}

_Bool isNoMaskBitSet(uint32_t x, uint32_t m){
    return (x&m) == 0; //returns 1 if no bits set in m are set in x
}

_Bool areAllMaskBitsSet(uint32_t x, uint32_t m){
    return (x&m) == m; //returns 1 if all bits set in m are set in x
}

uint32_t setMaskBits(uint32_t x, uint32_t m){
    return x|m; //returns x with mask bits set in m
}

uint32_t toggleMaskBits(uint32_t x, uint32_t m){
    return x^m; //returns x with the bits in m toggled
}

uint32_t clearMaskBits(uint32_t x, uint32_t m){
    return x&~m; //returns x with all bits set in m cleared
}

uint32_t getMaskBits(uint32_t x, uint32_t m){
    return x&m; //returns mask bits set in x
}

uint32_t getMaskBitsNotSet(uint32_t x, uint32_t m){
    return (x&m)^m; //returns mask bits not set in x
}

可以在单个 CPU 指令中在 0 和 1 之间翻转 bit/integer/bool 的任何可能代码

Any possible code that can flip a bit/integer/bool between 0 and 1 in single CPU instruction

c

c++

x86

assembly

micro-optimization

为什么 `bool` 与 `int` 不同？

那个额外的 `mov` 指令呢？

Why/How这样更好吗？

缓存

运营

分支

可读性

便携性

可以在单个 CPU 指令中在 0 和 1 之间翻转 bit/integer/bool 的任何可能代码

Any possible code that can flip a bit/integer/bool between 0 and 1 in single CPU instruction

c

c++

x86

assembly

micro-optimization

为什么 bool 与 int 不同？

那个额外的 mov 指令呢？

Why/How这样更好吗？

缓存

运营

分支

可读性

便携性

为什么 `bool` 与 `int` 不同？

那个额外的 `mov` 指令呢？