plasmacel plasmacel - 3 years ago 62
C++ Question

Bit trick to detect if any of some integers has a specific value

Is there any clever bit trick to detect if any of a small number of integers (say 3 or 4) has a specific value?

The straightforward

bool test(int a, int b, int c, int d)
// The compiler will pretty likely optimize it to (a == d | b == d | c == d)
return (a == d || b == d || c == d);

compiles to

test(int, int, int, int):
cmp ecx, esi
sete al
cmp ecx, edx
sete dl
or eax, edx
cmp edi, ecx
sete dl
or eax, edx

instructions have higher latency than I want to tolerate, so I would rather use something bitwise (
) stuff and a single comparison.

Answer Source

The only solution I've found yet is:

int s1 = ((a-d) >> 31) | ((d-a) >> 31);
int s2 = ((b-d) >> 31) | ((d-b) >> 31);
int s3 = ((c-d) >> 31) | ((d-c) >> 31);

int s = s1 & s2 & s3;
return (s&1) == 0;

it translates to:

mov     eax, ecx
sub     eax, edi
sub     edi, ecx
or      edi, eax
mov     eax, ecx
sub     eax, esi
sub     esi, ecx
or      esi, eax
and     esi, edi
mov     eax, edx
sub     eax, ecx
sub     ecx, edx
or      ecx, eax
test    esi, ecx
setns   al

which has less sete instructions, but obviously more mov/sub.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download