Test four int of commonality in the lower four bits

The four parameters a, b, c and d can be -1 (meaning it's not set) or a random one of {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}. If they are different from -1, they are guaranteed to be distinct.

The code looks at the four least significant bits of the four ints and tests if they all have a bit in common:

1101
1110
0100
0101

have the second left bit 1.

1001
1010
0000
0001

all have the second left bit 0.

1000
0110
0101
1101

have no common bit.

The following is possible:

a = -1, b = -1, c = 15, d =  4; //sim(a, b, c, d) == 0, because at least one is -1
a = -1, b = -1, c = -1, d = -1; //sim(a, b, c, d) == 0, because all are -1
a =  9, b =  1, c =  3, d =  5; //sim(a, b, c, d) == 1, because all values have a bit in common (a & 1, b & 1, c & 1 and d & 1 are all 1)
a =  8, b =  1, c =  2, d =  4; //sim(a, b, c, d) == 0, because there is no bit that is equal for a, b, c and d

The following will never happen:

a = 1, b = 1, c = 2, d = 5; // a == b, which is guaranteed to never happen because a == b

The code is meant to be as fast as possible on x86, readability would be a plus but is not necessary.

The code:

int sim(int a, int b, int c, int d)
{
    return ((a != -1) && (b != -1) && (c != -1) && (d != -1)) &&
    ((((a & 8) == (b & 8)) && ((a & 8) == (c & 8)) && ((a & 8) == (d & 8))) ||
     (((a & 4) == (b & 4)) && ((a & 4) == (c & 4)) && ((a & 4) == (d & 4))) ||
     (((a & 2) == (b & 2)) && ((a & 2) == (c & 2)) && ((a & 2) == (d & 2))) ||
     (((a & 1) == (b & 1)) && ((a & 1) == (c & 1)) && ((a & 1) == (d & 1))));
}

Are there obvious ways to speed up the code?

The code isn't bad, but it's a little more verbose than it needs to be. Consider that we don't really need to check one bit at a time; we can check four simultaneously.

The key here is that we're looking for bits that are the same in all four numbers. If we wanted to look for ones that were shared, we could do this:

a & b & c & d & 0xf

If we want to look for zeroes, we can simply invert:

~a & ~b & ~c & ~d & 0xf

If we put those together with the -1 part, it might look like this:

return a != -1 && b != -1 && c != -1 && d != -1 &&
    ((a & b & c & d) || (~a & ~b & ~c & ~d & 0xf));

However, the problem with this is that even though it's parallel, it still requires more operations than might be required.

If we consider the exclusive or function, it effectively return a 1 whenever the bits differ. So if there were only two numbers, we could do:

return (a ^ b) ^ 0xf;

The expression would only be false if all of the bits were different. We can use a similar strategy for three numbers.

return ((a ^ b) | (b ^ c)) ^ 0xf;

For this one, (a ^ b) returns 1 for every bit that is not the same between a and b, and the expression (b ^ c) returns 1 for every bit that is not the same between b and c. When we do a bitwise or of those quantities, only the the bits that are the same for all three quanties remain zeroes. When we do ^ 0xf we invert the bottom 4 bits so that only bits that are the same are ones.

Extrapolating this to four quantities,

return ((a ^ b) | (b ^ c) | (c ^ d)) ^ 0xf;

This is good but not sufficient since we still need to deal with the possible -1 quantities that may be among the inputs. One obvious way to do this is this:

return a != -1 && b != -1 && c != -1 && d != -1 &&
    (((a ^ b) | (b ^ c) | (c ^ d)) ^ 0xf);

To compare this routine which I'll call "Edward" to the one above, which I'll call "naive" to the original and the other three proposals so far, I used this code:

testcode.c

```
#include
#include
#include
#include
#include

bool sim(int a, int b, int c, int d)
{
return ((a != -1) && (b != -1) && (c != -1) && (d != -1)) &&
((((a & 8) == (b & 8)) && ((a & 8) == (c & 8)) && ((a & 8) == (d & 8))) ||
(((a & 4) == (b & 4)) && ((a & 4) == (c & 4)) && ((a & 4) == (d & 4))) ||
(((a & 2) == (b & 2)) && ((a & 2) == (c & 2)) && ((a & 2) == (d & 2))) ||
(((a & 1) == (b & 1)) && ((a & 1) == (c & 1)) && ((a & 1) == (d & 1))));
}

bool naive(int a, int b, int c, int d)
{
return a != -1 && b != -1 && c != -1 && d != -1 &&
((a & b & c & d) || (~a & ~b & ~c & ~d & 0xf));
}

bool edward(int a, int b, int c, int d)
{
return a != -1 && b != -1 && c != -1 && d != -1 &&
(((a ^ b) | (b ^ c) | (c ^ d)) ^ 0xf);
}

bool BitsInCommon(int a, int b, int c, int d)
{
if (a == -1 || b == -1 || c == -1 || d == -1)
return false;

int rslt = 0;
rslt = (a & 15) & (b & 15) & (c & 15) & (d & 15);
if (rslt != 0)
return true;

//check for zero bits in common??? if needed?
rslt = ((a ^ -1) & 15) & ((b ^ -1) & 15) & ((c ^ -1) & 15) & ((d ^ -1) & 15);

return rslt != 0;
}

bool jan_korous(int a, int b, int c, int d) {

if( a == -1 || b == -1 || c == -1 || d == -1 ) { return 0; }

const unsigned int diff = (a ^ b) | (c ^ d) | (a ^ c);

return
( (diff & 1) == 0 ) ||
( (diff & 2) == 0 ) ||
( (diff & 4) == 0 ) ||
( (diff & 8) == 0 );

}

bool scottbb(int a, int b, int c, int d) {
if (a == -1 || b == -1 || c == -1 || d == -1) {
return 0;
}
else {
unsigned int all_1 = (unsigned int)a & (unsigned int)b &
(unsigned int)c & (unsigned int)d;
unsigned int all_0 = ~((unsigned int)a | (unsigned int)b |
(unsigned int)c | (unsigned int)d);
return (all_1 | (all_0 & 0xF)) ? 1 : 0;
}
}

int main()
{
bool troubleshoot = false;
struct {
const char *name;
bool (*func)(int, int, int, int);
double elapsed;
bool isCorrect;
} tests[] = {
{ "original", sim, 0, true },
{ "naive", naive, 0, true },
{ "Edward", edward, 0, true },
{ "dbasnett", BitsInCommon, 0, true },
{ "Jan Korous", jan_korous, 0, true },
{ "scottbb", scottbb, 0, true},
{ NULL, NULL, 0, false}
};
// see if they're all correct
for (int a = -1; a %d, should have been %d\n",
tests[i].name, a, b, c, d,
tests[i].func(a, b, c, d),
tests[0].func(a, b, c, d)
);
}
tests[i].isCorrect = false;
if (troubleshoot)
return -1;
}
}
}

StackExchange Code Review Q#131694, answer score: 8