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 &amp; 1, b &amp; 1, c &amp; 1 and d &amp; 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) &amp;&amp; (b != -1) &amp;&amp; (c != -1) &amp;&amp; (d != -1)) &amp;&amp;
    ((((a &amp; 8) == (b &amp; 8)) &amp;&amp; ((a &amp; 8) == (c &amp; 8)) &amp;&amp; ((a &amp; 8) == (d &amp; 8))) ||
     (((a &amp; 4) == (b &amp; 4)) &amp;&amp; ((a &amp; 4) == (c &amp; 4)) &amp;&amp; ((a &amp; 4) == (d &amp; 4))) ||
     (((a &amp; 2) == (b &amp; 2)) &amp;&amp; ((a &amp; 2) == (c &amp; 2)) &amp;&amp; ((a &amp; 2) == (d &amp; 2))) ||
     (((a &amp; 1) == (b &amp; 1)) &amp;&amp; ((a &amp; 1) == (c &amp; 1)) &amp;&amp; ((a &amp; 1) == (d &amp; 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 &amp; b &amp; c &amp; d &amp; 0xf


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

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


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

return a != -1 &amp;&amp; b != -1 &amp;&amp; c != -1 &amp;&amp; d != -1 &amp;&amp;
    ((a &amp; b &amp; c &amp; d) || (~a &amp; ~b &amp; ~c &amp; ~d &amp; 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 &amp;&amp; b != -1 &amp;&amp; c != -1 &amp;&amp; d != -1 &amp;&amp;
    (((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 &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
#include &lt;time.h&gt;
#include &lt;math.h&gt;
#include &lt;stdbool.h&gt;

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

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

bool edward(int a, int b, int c, int d)
{
    return a != -1 &amp;&amp; b != -1 &amp;&amp; c != -1 &amp;&amp; d != -1 &amp;&amp;
        (((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 &amp; 15) &amp; (b &amp; 15) &amp; (c &amp; 15) &amp; (d &amp; 15);
    if (rslt != 0)
        return true;

    //check for zero bits in common???  if needed?
    rslt = ((a ^ -1) &amp; 15) &amp; ((b ^ -1) &amp; 15) &amp; ((c ^ -1) &amp; 15) &amp; ((d ^ -1) &amp; 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 &amp; 1) == 0 ) || 
        ( (diff &amp; 2) == 0 ) || 
        ( (diff &amp; 4) == 0 ) || 
        ( (diff &amp; 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 &amp; (unsigned int)b &amp;
                             (unsigned int)c &amp; (unsigned int)d;
        unsigned int all_0 = ~((unsigned int)a | (unsigned int)b |
                               (unsigned int)c | (unsigned int)d);
        return (all_1 | (all_0 &amp; 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 &lt; 16; ++a) {
        for (int b = -1; b &lt; 16; ++b) {
            for (int c = -1; c &lt; 16; ++c) {
                for (int d = -1; d &lt; 16; ++d) {
                    for (size_t i = 1; tests[i].func; ++i) {
                        if (tests[i].func(a,b,c,d) != tests[0].func(a,b,c,d)) {
                            if (troubleshoot) {
                                printf("%s failed! [%d, %d, %d, %d] =&gt; %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;
                        }
                    }
                }
            }
        }
    }

    puts("All functions checked for accuracy; checking timing...");
    for (int iterations = 100; iterations; --iterations) {
        for (size_t i = 0; tests[i].func; ++i) {
            if (tests[i].isCorrect) {
                for (int a = -1; a &lt; 16; ++a) {
                    for (int b = -1; b &lt; 16; ++b) {
                        for (int c = -1; c &lt; 16; ++c) {
                            for (int d = -1; d &lt; 16; ++d) {
                                clock_t start = clock();
                                tests[i].func(a,b,c,d);
                                tests[i].elapsed += clock() - start;
                            }
                        }
                    }
                }
            }
        }
    }
    // print results
    for (size_t i = 0; tests[i].func; ++i) {
        if (tests[i].isCorrect) {
            printf("%12s\t%.10f\t%f%% %s than %s\n", tests[i].name, tests[i].elapsed,
                100.0*fabs(tests[i].elapsed-tests[0].elapsed)/tests[0].elapsed, 
                (tests[i].elapsed &gt; tests[0].elapsed ? "slower" : "faster"),
                tests[0].name
            );
        } else {
            printf("%12s\twas not correct; no time recorded\n", tests[i].name);
        }
    }
}


Results:

Note: I've updated the results to include everybody's correct versions and to include the two solutions proposed by @js1 although I didn't bother duplicating the source code for those solutions in the code above.


All functions checked for accuracy; checking timing...
    original    1052389.0000000000  0.000000% faster than original
       naive    1034792.0000000000  1.672100% faster than original
      Edward    1024637.0000000000  2.637048% faster than original
    dbasnett    1032151.0000000000  1.923053% faster than original
  Jan Korous    1028349.0000000000  2.284326% faster than original
     scottbb    1026372.0000000000  2.472185% faster than original
         JS1    1035062.0000000000  1.646444% faster than original
  JS1 Lookup    1023049.0000000000  2.787942% faster than original


So in my tests, on a quad-core x86_64 machine, the Edward and Jan Korous routines are nearly identical in time and both are a small improvement (approximately 2%) over the original.  There was a slight but persistent speed advantage to the "JS1 Lookup" version on this machine.

Compile command (Linux) was:


  gcc -O2 -std=c99 testcode.c -o testcode &amp;&amp; ./testcode


On a quad core ARM7, I got this result with the same code:


All functions checked for accuracy; checking timing...
    original    17302157.0000000000 0.000000% faster than original
       naive    17211229.0000000000 0.525530% faster than original
      Edward    17231692.0000000000 0.407261% faster than original
    dbasnett    17255411.0000000000 0.270174% faster than original
  Jan Korous    17115011.0000000000 1.081634% faster than original
     scottbb    17120390.0000000000 1.050545% faster than original
         JS1    17267606.0000000000 0.199692% faster than original
  JS1 Lookup    17118642.0000000000 1.060648% faster than original


I also tested on Windows under Cygwin, but found that the variability in timing on that platform was so large as to render the test results meaningless.  As an example, here are four successive runs on that platform:


All functions checked for accuracy; checking timing...
    original    1902.0000000000 0.000000% faster than original
       naive    2124.0000000000 11.671924% slower than original
      Edward    2182.0000000000 14.721346% slower than original
    dbasnett    2091.0000000000 9.936909% slower than original
  Jan Korous    1980.0000000000 4.100946% slower than original
     scottbb    2144.0000000000 12.723449% slower than original
         JS1    2276.0000000000 19.663512% slower than original
  JS1 Lookup    2075.0000000000 9.095689% slower than original
All functions checked for accuracy; checking timing...
    original    2174.0000000000 0.000000% faster than original
       naive    2121.0000000000 2.437902% faster than original
      Edward    2088.0000000000 3.955842% faster than original
    dbasnett    2055.0000000000 5.473781% faster than original
  Jan Korous    2136.0000000000 1.747930% faster than original
     scottbb    2109.0000000000 2.989880% faster than original
         JS1    1855.0000000000 14.673413% faster than original
  JS1 Lookup    2149.0000000000 1.149954% faster than original
All functions checked for accuracy; checking timing...
    original    2073.0000000000 0.000000% faster than original
       naive    2154.0000000000 3.907381% slower than original
      Edward    1960.0000000000 5.451037% faster than original
    dbasnett    2288.0000000000 10.371442% slower than original
  Jan Korous    2032.0000000000 1.977810% faster than original
     scottbb    2091.0000000000 0.868307% slower than original
         JS1    2245.0000000000 8.297154% slower than original
  JS1 Lookup    2138.0000000000 3.135552% slower than original
All functions checked for accuracy; checking timing...
    original    2158.0000000000 0.000000% faster than original
       naive    2277.0000000000 5.514365% slower than original
      Edward    1840.0000000000 14.735867% faster than original
    dbasnett    2081.0000000000 3.568119% faster than original
  Jan Korous    2135.0000000000 1.065802% faster than original
     scottbb    2228.0000000000 3.243744% slower than original
         JS1    1969.0000000000 8.758109% faster than original
  JS1 Lookup    2010.0000000000 6.858202% faster than original