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

Question

Can a single x86 instruction toggle a boolean value between '0' and '1'?

I thought of following ways but all result in two instruction with -O3 flag of gcc.

status =! status;

status = 1 - status;

status  = status == 0 ? 1: 0;

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

Is there a faster way to do this?

This is what I tried: https://godbolt.org/g/A3qNUw

---

What I need is a function which toggles the input and returns, written in a way that compiles to one instruction. Something similar to this function:

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

compiles on Godbolt to this:

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

Answer 1

To flip a bit in an integer, use xor like this: foo ^= 1.

gcc knows this optimization already for bool, so you can return !status; like a normal person without losing any efficiency. gcc does compile status ^= 1 to an xor instruction as well. In fact, all your ideas except the table lookup compile to a single xor instruction with bool input / return value.

Check it out on the Godbolt compiler explorer with gcc -O3, with asm output panes for bool and 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

Semi-related: XOR is add-without-carry. So if you only care about the low bit, you can copy-and-flip-low with lea eax, [rdi+1]. See Check if a number is even where that's useful in combination with and eax, 1 to get it done in 2 instructions.

---

Why is bool different from int?

The x86-64 System V ABI requires that callers passing a bool pass a 0 or 1 value, not just any non-zero integer. Thus, the compiler can assume that about the input.

But with int foo, the C expression !foo requires "booleanizing" the value. !foo has type _Bool / (aka bool if you #include <stdbool.h>), and converting that back to an integer must produce a value of 0 or 1. If the compiler doesn't know that foo must be 0 or 1, it can't optimize !foo to foo^=1, and can't realize that foo ^= 1 flips a value between truthy / falsy. (In the sense that if(foo) means if(foo != 0) in C).

This is why you get test/setcc (zero-extended into a 32-bit int by xor-zeroing a register before the test).

Related: Boolean values as 8 bit in compilers. Are operations on them inefficient?. Stuff like (bool1 && bool2) ? x : y isn't always compiled as efficiently as you might hope. Compilers are pretty good, but do have missed-optimization bugs.

---

What about that extra mov instruction?

It will go away when inlining, if the compiler doesn't need / want to keep the old un-flipped value around for later. But in a stand-alone function, the first arg is in edi, and the return value needs to be in eax (in the x86-64 System V calling convention).

Tiny functions like this are a close approximation to what you might get as part of a large function (if this flip couldn't be optimized into something else), but needing the result in a different register is a confounding factor.

---

x86 doesn't have a copy-and-xor integer instruction, so for a stand-alone function it will take at least a mov to copy from the arg-passing register to eax.

lea is special: it's one of the few integer ALU instructions that can write the result to a different register instead of destroying its input. lea is a copy-and-shift/add instruction, but there's no copy-and-xor instruction in x86. Many RISC instruction sets have 3-operand instructions, for example MIPS could do xor $t1, $t2, $t3.

AVX introduced non-destructive versions of vector instructions (saving a lot of movdqa / movups register-copying in a lot of code), but for integer there are only a few new instructions that do different things. rorx eax, ecx, 16 for example does eax = rotate_right(ecx, 16), and uses the same VEX encoding that non-destructive AVX instructions use.

Answer 2

From this code run of Godbolt (This code basically contains few of the options I tried) it seems XORing gives a one statement which can do it:-(As you said toggling is what you are looking for)

status ^= 1;

boils down to just single instruction of (this was with -O0)

xor DWORD PTR [rbp-4], 1

With -O3 you can see all the methods you mentioned use xor anf this inparticular comes to mov eax, edi/xor eax, 1.

And this ensures the state being toggled to and fro from 0 to 1 and vice versa. (Because there is xor statement - which is there in most architectures and useful in many cases).

I have let the other option of memory access fall through - because pointer arithmetic and dereferecing the address would not be faster than these ones (have possible memory access).

I have suggested one way of doing based on the small messing around in godbolt. What you can do from here is - compare different ways of doing it and then get a result of time you are getting. Supposedly, the result you will get XOR-ing won't be that bad on your machine's architecture.

Interestingly as Peter Cordes in the example showed that this would hold true for booleans also.

With this example it is clear that compiler optimizes to the unoptimized code's xoring with 1 version. This is one way supports the fact that xoring would yield better result in case of normal int operation. With booleans when compiled using -O3 all the ones shown above trickles to mov eax, edi/xor eax, 1.

Answer 3

If you are down to trying to micro-optimize boolean operations, you are either prematurely optimizing or you are doing a lot of operations on a lot of boolean data. For the former - The answer is don't; for the latter, you may be asking the wrong question. If the real question is how do I optimize (many) operations on (much) boolean data, the answer is to use an alternative representation based on "flags" (a.k.a. use a better algorithm). This will allow you to portably and readably fit more data into cache and perform multiple operations and tests simultaneously.

Why/How is this better?

Cache

Consider a system where the cache line size is 64 bytes. 64 _Bool will fit into the data cache line whereas 8 times that amount will fit. You'll likely have smaller instruction code as well - ranging from 1 additional instruction to 32x fewer. This can make a large difference in tight loops.

Operations

Most operations involve one or two (usually very fast) operations and a single test regardless of how many flags you are testing. Since this can incorporate multiple values simultaneously, each operation can do (typically 32 or 64 times) more work.

Branching

Since multiple operations and tests can be completed simultaneously, what would have been up to 32 (or 64) possible branches can be reduced to one. This can reduce branch mispredictions.

Readability

By using a well named mask constant, a complex nested if-else-if-else block can be reduced to a single readable line.

Portability

_Bool was not available in early versions of C and C++ uses different mechanisms for boolean; however, flags will work in older versions of C and is compatible with C++

Here is a practical example of how to set a mask with flags:

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

This concept can be used to simultaneously operate on a simulated array of boolean values using something like:

//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
}