java - Finding all combinations of longs with certain bits set

Question

This is such an obscure problem that I suspect I'll have to do it at a different level in my code...but hopefully the hive mind that is Stack Overflow can help...

I have a long, which if expressed as a binary string will have exactly five bits set. For example,

long l = 341; // as a bit string, "101010101"

I'm seeking an array containing all ten possible longs which exactly three of those bits set. To continue the example,

long[] results = {
  101010000,
  101000100,
  101000001,
  100010100,
  100010001,
  100000101,
    1010100,
    1010001,
    1000101,
      10101
}

Here's what the appropriate method signature might look like:

public long[] toThreeBitCombinations(long l) {
    // what goes here?
}

(The problem domain is poker; enumerating all the possible board card combinations in a Omaha Poker hand. Yep, there are other ways to approach this, but I am testing out this approach, as dealing with bits is so much quicker than most other alternatives.)

Answer 1

Well, I got it. I think. I constructed a version of Gosper's Hack for fragmented fields that I'm not entirely sure about, but it worked for this case.

static long next(long v, long m)
{
    long t = v | (v - 1 & m);
    long t1 = (((t | ~m) + 1) & m);
    int c = Long.numberOfTrailingZeros(v) + 2; // *
    long w = t1 | (((~t & t1) - 1 & m) >>> c);
    return w;
}

I'm not sure why the 2 in the line marked with an asterisk is a 2 instead of a 1.

Anyway, if you do x = next(x, 0x155) in a loop (start with x = 0x15 of course) you get those ten things you listed.