First alternative solution
As mentioned in several other answers already, you can do many of the computations in parallel 4 bits at a time. To check whether all four numbers have a 1-bit in the same column, you can use:
if (a & b & c & d)
return true;
To check whether all four numbers have a 0-bit in the same column, you can use:
if ((a | b | c | d) ^ 0xf)
return true;
One trick that no one else has mentioned yet is that you can detect if any number is -1 in parallel as well, like this:
if ((a | b | c | d) == -1)
return false;
Since there is a common expression between this and the previous check, you can save time by computing that expression once. Therefore, the complete solution is:
bool js1(int a, int b, int c, int d)
{
int totalOr = a | b | c | d;
return (totalOr != -1) && ((totalOr ^ 0xf) || (a & b & c & d));
}
Actually I found after doing timing tests that this ordering seems to be faster, probably because the if statement short circuits more often:
bool js1_reordered(int a, int b, int c, int d)
{
int totalOr = a | b | c | d;
return ((totalOr ^ 0xf) || (a & b & c & d)) && (totalOr != -1);
}
Second alternative solution
Another thing that I haven't seen mentioned yet is that the problem is small enough that you can construct a lookup table that holds every answer. In total, there are 16*16*16*16 = 65536
possibilities, which only requires an 8 KB table to store the answers (1 bit per answer). Assuming your computer's L1 cache is larger than 8 KB, you may be able to achieve faster speeds with a lookup table.
Here is my solution using a lookup table:
static uint16_t js1_table[0x1000];
void build_table(void)
{
for (int a=0; a<16; a++) {
for (int b=0; b<16; b++) {
for (int c=0; c<16; c++) {
for (int d=0; d<16; d++) {
if (((a | b | c | d) ^ 0xf) || (a & b & c & d)) {
unsigned int index = (a << 8) | (b << 4) | c;
js1_table[index] |= (1 << d);
}
}
}
}
}
}
bool js1_lookup(int a, int b, int c, int d)
{
unsigned int index = (a << 8) | (b << 4) | c;
if (index >= 0x1000)
return false;
return js1_table[index] & (1 << d);
}
The -1 detection works in a tricky way:
- If any of
a
, b
, or c
is -1, then the index
computed will have high bits set and will be greater than 0x1000, thus causing the function to return false. This also doubles as a bounds check to prevent accessing past the end of the lookup table.
- If
d
is -1, then 1 << d
will be 0, and anything anded with 0 will become 0, so the function will return false.
Timings
I used Edward's timing program but I modified the timing loop to reduce jitter by moving the call to clock()
to the outermost loop so that it is called only once per test instead of once per function call. The drawback is that the loop overhead shows up in the final time, but since this overhead is the same for all tests, the relative speed of each solution is preserved. The absolute speed could theoretically be determined by measuring and subtracting the loop overhead, but I didn't bother to do that.
Here is the complete test program for reference:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include <stdbool.h>
#include <stdint.h>
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 js1(int a, int b, int c, int d)
{
int totalOr = a | b | c | d;
return (totalOr != -1) && ((totalOr ^ 0xf) || (a & b & c & d));
}
bool js1_reordered(int a, int b, int c, int d)
{
int totalOr = a | b | c | d;
return ((totalOr ^ 0xf) || (a & b & c & d)) && (totalOr != -1);
}
static uint16_t js1_table[0x1000];
void build_table(void)
{
for (int a=0; a<16; a++) {
for (int b=0; b<16; b++) {
for (int c=0; c<16; c++) {
unsigned int index = (a << 8) | (b << 4) | c;
for (int d=0; d<16; d++) {
if (((a | b | c | d) ^ 0xf) || (a & b & c & d))
js1_table[index] |= (1 << d);
}
}
}
}
}
bool js1_lookup(int a, int b, int c, int d)
{
unsigned int index = (a << 8) | (b << 4) | c;
if (index >= 0x1000)
return false;
return js1_table[index] & (1 << d);
}
bool BitsInCommon(int a, int b, int c, int d)
{
if (a == -1 || b == -1 || c == -1 || d == -1)
return false;
if (((a & b & c & d) & 0xf) != 0)
return true;
return (((a ^ -1) & (b ^ -1) & (c ^ -1) & (d ^ -1)) & 0xf) != 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 },
{ "JS1", js1, 0, true },
{ "JS1 Reordered", js1_reordered, 0, true },
{ "JS1 Lookup", js1_lookup, 0, true },
{ "dbasnett", BitsInCommon, 0, true },
{ "Jan Korous", jan_korous, 0, true },
{ "scottbb", scottbb, 0, true},
{ NULL, NULL, 0, false}
};
build_table();
// see if they're all correct
for (int a = -1; a < 16; ++a) {
for (int b = -1; b < 16; ++b) {
for (int c = -1; c < 16; ++c) {
for (int d = -1; d < 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] => %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 (size_t i = 0; tests[i].func; ++i) {
if (tests[i].isCorrect) {
clock_t start = clock();
for (int iterations = 10000; iterations; --iterations) {
for (int a = -1; a < 16; ++a) {
for (int b = -1; b < 16; ++b) {
for (int c = -1; c < 16; ++c) {
for (int d = -1; d < 16; ++d) {
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 > tests[0].elapsed ? "slower" : "faster"),
tests[0].name
);
} else {
printf("%12s\twas not correct; no time recorded\n", tests[i].name);
}
}
}
And here is the output when run on my computer (built with gcc -O2
on 64-bit Linux). Note: I originally had run these tests on 32-bit Cygwin, but it appears that the timings run more accurately on Linux:
All functions checked for accuracy; checking timing...
original 4680000.0000000000 0.000000% faster than original
naive 2580000.0000000000 44.871795% faster than original
Edward 2380000.0000000000 49.145299% faster than original
JS1 2530000.0000000000 45.940171% faster than original
JS1 Reordered 2240000.0000000000 52.136752% faster than original
JS1 Lookup 1920000.0000000000 58.974359% faster than original
dbasnett 2610000.0000000000 44.230769% faster than original
Jan Korous 2340000.0000000000 50.000000% faster than original
scottbb 2530000.0000000000 45.940171% faster than original
Frequency distribution affects algorithm
You didn't mention anything about the frequency distribution in the problem statement. For example, how often does -1 appear? Do the numbers 0..15 all appear with equal frequency? The "fastest" algorithm could depend on the answers to the above questions. For example, if -1 appears very often, then the check that determines if any of the four numbers is -1 becomes very important and may need adjusting. For example, the straightforward method
if (a == -1 || b == -1 || c == -1 || d == -1)
return false;
might be the best because it will likely short circuit early and return quicker than something like this which has to always do three ORs:
if ((a | b | c | d) == -1)
return false;