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.

Answer 2

I also tried to adapt the standard algorithm for enumerating combinations of a complete set of bits. That algorithm finds the lowest group of 1-bits, moves the highest bit one to the left, and shifts the other ones to the bottom. So for our case, we need to find the k lowest set bits. I didn't have any idea how to do that without a loop, which assumes a fast "popcount" instruction is available (count the number of 1-bits):

unsigned next_combination(unsigned comb, unsigned set) {
    unsigned h = (-comb & (comb ^ set)) - 1;
    unsigned l = set;
    for (int i = 0; i < popcount(h & comb) - 1; ++i)
        l &= l - 1;
    comb = (set & h) ^ l;
    return comb;
}

Edit: I found a different approach that does without the popcount at the chess programming wiki: Traversing Subsets of a Set. It can be slightly simplified as follows:

unsigned next_combination(unsigned comb, unsigned set) {
    unsigned tmp = comb - 1;
    unsigned rip = set & ((tmp | comb) - set);
    for (comb = (tmp ^ rip) & comb; comb; rip ^= tmp, set ^= tmp) {
        tmp = set & -set;
        comb &= comb - 1;
    }
    return rip;
}

Since the loop is only executed once on average, this seems to be actually slightly faster on my machine, probably also because of the bad latency of popcount.