/*

Brad Reimer (breimer@ea.com)

EATech (tools and libs) at EAC

TECHNIQUE:

Simply walk through bit combinations in loops until all matches found

11110000 00000000 00000000 00000000 00000000 00000000 00000000 00000000

11101000 00000000 00000000 00000000 00000000 00000000 00000000 00000000

...

11100000 00000000 00000000 00000000 00000000 00000000 00000000 00000001

11011000 00000000 00000000 00000000 00000000 00000000 00000000 00000000

...

DISCUSSION:

I attempted several variations of this code using unrolled loops (usually

exploiting the fact that for every 64-bit answer, there also existed an

answer with the two 32-bit halves swapped). Many of these had faster

performance on my home computer (an AMD Athlon 64), but this --one of my

original attempts at the problem-- always performed best on my work

machine (an Intel P4).

*/

void Choose64_4_breimer(unsigned __int64 *pDest)

{

const int NumBits = 64;

const unsigned __int64 One = 1uLL;

unsigned __int64 *cur = pDest;

unsigned __int64 xval, yval, zval, wval;

unsigned __int64 xyval, xyzval;

xval = One;

for (int x = 0; x < NumBits; ++x)

{

yval = (xval << 1);

for (int y = x+1; y < NumBits; ++y)

{

xyval = xval | yval;

zval = (yval << 1);

for (int z = y+1; z < NumBits; ++z)

{

xyzval = xyval | zval;

wval = (zval << 1);

for (int w = z+1; w < NumBits; ++w)

{

*(cur++) = xyzval | wval;

wval <<= 1;

}

zval <<= 1;

}

yval <<= 1;

}

xval <<= 1;

}

}