Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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);
}

in GCC 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
        ret

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

like image 820
plasmacel Avatar asked Jul 24 '17 21:07

plasmacel


People also ask

How do you find the bit of an integer?

Here we create a mask, apply the mask to n, and then right shift the masked value to get just the bit we want. We could write it out more fully as: int mask = 1 << k; int masked_n = n & mask; int thebit = masked_n >> k; You can read more about bit-masking here.

Are integers always 32 bit?

int is always 32 bits wide. sizeof(T) represents the number of 8-bit bytes (octets) needed to store a variable of type T . (This is false because if say char is 32 bits, then sizeof(T) measures in 32-bit words.) We can use int everywhere in a program and ignore nuanced types like size_t , uint32_t , etc.

How do you know if a single bit is set?

Check whether the K-th bit is set or not Using Left Shift Operator: To solve the problem follow the below idea: Left shift given number 1 by k-1 to create a number that has only set bit as k-th bit. If bitwise AND of n and temp is non-zero, then result is SET else result is NOT SET.

How do you know if two bits are set?

Bitwise AND Operator (&) is used to check whether a bit is SET (HIGH) or not SET (LOW) in C and C++ programming language. Bitwise AND Operator (&) is a binary operator, which operates on two operands and checks the bits, it returns 1, if both bits are SET (HIGH) else returns 0.


1 Answers

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;

alternative variant:

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

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

both are translated 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
ret

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

Update: as BeeOnRope@ suggested - it makes sense to cast input variables to unsigned

like image 57
Iłya Bursov Avatar answered Oct 12 '22 17:10

Iłya Bursov