CODEWITHSUNDEEP
cx86bit-manipulationbitwise-operators
adigostin
adigostin

Reputation: 637

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

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.

Upvotes: 1

Views: 711

Answers (2)

Aki Suihkonen
Aki Suihkonen

Reputation: 20067

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

Upvotes: 3

chqrlie
chqrlie

Reputation: 145297

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.

Upvotes: 3

Related Questions