在单CPU指令中,任何可能在0和1之间翻转位/整数/布尔值的代码

要在整数中翻转位,请使用 xor 这样地: foo ^= 1 .

gcc已经知道此优化 bool ,所以您可以 return !status; 就像一个普通人一样,不会失去任何效率。gcc编译 status ^= 1 到xor指令。事实上,除了查表之外,您的所有想法都可以编译为一个 异或 使用说明 布尔 输入/返回值。

过来看 on the Godbolt compiler explorer 具有 gcc -O3 ,带有asm输出窗格 布尔 和 int .

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

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

vs。

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

为什么是 布尔 不同于 内景 ?

The x86-64 System V ABI 要求调用方传递 布尔 传递0或1值,而不仅仅是任何非零整数。因此,编译器可以假设关于输入。

但是有 int foo ,C表达式 !foo 需要“布尔化”值。 !foo公司 具有类型 _Bool /(又名 布尔 如果你 #include <stdbool.h> ),将其转换回整数必须生成0或1的值。如果编译器不知道 foo 必须是 0 或 1 ,无法优化 !foo公司 到 foo^=1 ,但我没意识到 foo^=1 在truthy/falsy之间翻转值。(在某种意义上 if(foo) 方法 if(foo != 0) 在C)中)。

这就是为什么要将test/setcc(零扩展为32位 内景 通过 xor -zeroing a register 在 test ).

相关: Boolean values as 8 bit in compilers. Are operations on them inefficient? . 比如 (bool1 && bool2) ? x : y 并非总是像您希望的那样高效地编译。编译器相当不错,但确实遗漏了优化bug。

那额外的呢 mov 指示

内联时会消失 ,如果编译器不需要/不想为以后保留旧的未翻转值。但在独立函数中,第一个参数位于 edi ,返回值需要在 eax (在x86-64 System V调用约定中)。

像这样的小函数与作为大函数的一部分可能得到的结果非常接近(如果此翻转无法优化为其他函数),但需要在不同寄存器中得到结果是一个令人困惑的因素。

x86没有复制和异或整数指令 ,因此,对于一个独立函数,至少需要 压敏电阻 从arg传递寄存器复制到 eax公司 .

lea 是特别的 :它是为数不多的整数ALU指令之一,可以将结果写入不同的寄存器,而不是销毁其输入。 lea公司 是一个 copy-and-shift/add instruction ,但x86中没有copy和xor指令。许多RISC指令集都有3个操作数的指令,例如MIPS可以 xor $t1, $t2, $t3 .

AVX引入了矢量指令的非破坏性版本(节省了大量 movdqa / movups 在许多代码中注册复制),但对于integer,只有少数新指令执行不同的操作。 rorx eax, ecx, 16 例如 eax = rotate_right(ecx, 16) ,并使用与非破坏性AVX指令相同的VEX编码。

从这个 code run of Godbolt (这段代码基本上包含了我尝试过的几个选项)似乎XORing给出了一个可以做到这一点的语句:-(正如您所说的,切换就是您要寻找的)

status ^= 1;

归结为的单个指令 -O0 )

xor DWORD PTR [rbp-4], 1

具有 -O3 您可以看到您提到的所有使用的方法 xor 尤其是 mov eax, edi/xor eax, 1 .

这确保了状态在 0 到 1 反之亦然。(因为有 异或 语句—这在大多数体系结构中都存在,在许多情况下都很有用)。

我让内存访问的另一种选择落空了,因为指针算法和对地址的解引用不会比这两种更快(可能会有内存访问)。

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

有趣的是,Peter Cordes在这个例子中 showed 这也适用于布尔人。

用这个 example 很明显,编译器会优化到未优化代码的xoring 1. 版本这是一种支持这样一个事实的方法,即在正常int操作的情况下,xoring将产生更好的结果。使用编译时使用布尔值 -O3 以上所示的所有内容都会 mov eax,edi/xor eax,1 .

如果您开始尝试微优化布尔运算,那么您要么过早优化,要么对大量布尔数据执行大量操作。对于前者,答案是不要;对于后者,你可能问错了问题。如果真正的问题是如何优化(许多)布尔数据上的(许多)操作,那么答案是使用基于“标志”的替代表示(即使用更好的算法)。这将允许您以可移植和可读的方式将更多数据放入缓存,并同时执行多个操作和测试。

为什么/如何更好?

隐藏物

考虑一个缓存线大小为64字节的系统。64 _Bool 将放入数据缓存线,而容量是该容量的8倍。您可能会有更小的指令代码,从1条额外指令到32条更少的指令。这会在紧密循环中产生很大的不同。

操作

大多数操作都涉及一个或两个(通常非常快)操作和一个测试,而不管您要测试多少个标志。由于这可以同时合并多个值,因此每个操作可以做(通常是32或64倍)更多的工作。

分支

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

可读性

通过使用一个命名良好的掩码常量 if-else-if-else 块可以减少到一个可读的行。

可移植性

_Bool在早期版本的C中不可用,C++对boolean使用不同的机制;但是,标志将在旧版本的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
}