Hacker's Delight #6 - "64 choose 4"
Consider all the possible combinations of 4 bits in a 64-bit word. Obviously, there are 635,376 possible combinations *
* given by { 64 choose 4 } or factorial(64) / (factorial(4) * factorial(64 - 4))
Some examples are:
0x000000000000000f (binary 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 1111) four bits set
0x0000000000000017 (binary 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0001 0111) four bits set
0x0200400400000010 (binary 0000 0010 0000 0000 0100 0000 0000 0010 0000 0000 0000 0000 0000 0000 0001 0000) four bits set
0x0020020014000000 (binary 0000 0000 0010 0000 0000 0010 0000 0000 0001 0100 0000 0000 0000 0000 0000 0000) four bits set
The task is to enumerate each of these unique combinations (such as above) exactly once until all 635,376 have been written into an array. Although order does not matter, no value can be duplicated.
The naïve approach is to iterate from 0 to 0xffffffffffffffff and check each value to see if it has exactly four bits. This would take around 2,300 years on our standard dev machines. We will consider this approach to be "sub-optimal". This is one of those problems where the right approach makes all the difference...
Challenge: Write the fastest function possible to enumerate all possible combinations of 4 bits in a 64-bit word.
You will be provided with an array of unsigned __int64 of length 635,376. Write x86 code to fill this array, and assume your function will be run on a standard P4 dev machine. C, C++, __asm blocks, SSE, MMX, are all acceptable. You are allowed to use pre-built buffers and call out to other functions.
Assume that your code will be compiled with /O2, exceptions off, and SSE2 extensions turned on.
You must use a function prototype that follows the following syntax, decorated with your name. No calling convention modifiers may be used.
Please replace "jhejl" with your name. (An amazing number of people submit entries with my name on them).
void Choose64_4_jhejl(unsigned __int64 *pDest);
Good luck,
HD Team
Email entries to: jhejl@ea.com
DUE DATE EXTENDED : Saturday, Sept 2nd by midnight