C bit twiddling so that int 0 becomes 1, while any non-zero becomes -1? (ideally x86 intrinsic)

Viewed 261

I'm looking for a way to achieve what I wrote in the title. I'm doing it now with an "if" and I want to get rid of branching. I've had a look at a couple of pages such as this one, can't find the exact thing I'm looking for.

3 Answers

Converting x to a boolean does not generate any branches on current x86 processors. You can use simple arithmetics to generate your result:

int test_zero(int x) {
    return 1 - 2 * !!x;
}

gcc 11.2 generates this:

test_zero:
    cmp     edi, 1
    sbb     eax, eax
    and     eax, 2
    sub     eax, 1
    ret

clang 13.0.0 generates this:

test_zero:                              # @test_zero
    xor     eax, eax
    test    edi, edi
    sete    al
    add     eax, eax
    add     eax, -1
    ret

As commented by dratenik, even simpler and more readable source compiles to exactly the same branchless executable code:

int test_zero2(int x) {
    return x ? -1 : 1;
}

You check the code generation on Godbolt's compiler explorer.

The clang/gcc output (from the answer by chqrlie) could be truncated a bit to

cmp  edi, 1
sbb  eax, eax
or   eax, 1

After sbb eax, eax we have eax == 0 for edi != 0. But since -1 and 1 both have the LSB set, we can just make it so.

Alas, even if we can produce a two instruction sequence for

int test_zero_3(int x) {
   return x ? -1 : 0;
}
...
neg     edi
sbb     eax, eax
 

we can't fool clang, but we can make gcc to produce the expected (or closely equivalent) sequence

int test_zero_4(int x) {
   return (test_zero_3(x)) | 1;
}
...
neg     edi
sbb     eax, eax
or      eax, 1

Without bit-wise operation, you can do something like:

int func(int x)
{
    return int(uint(x-1) / uint(-1)) * 2 - 1;
}

Or:

int func(int x)
{
    return int(uint(~x) / uint(~0)) * 2 - 1;
}
Related