查找设置了某些位的所有长整型组合

Question

这是一个

如此晦涩的问题，我怀疑我将不得不在我的代码中的不同级别来做......但希望堆栈溢出的蜂巢思维可以提供帮助......

我有一个长，如果表示为二进制字符串，将正好设置五个位。例如

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

我正在寻找一个包含所有十个可能的长整型的数组，其中正好是其中三个位设置的。继续该示例，

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

下面是相应的方法签名可能的样子：

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

(问题域是扑克;枚举奥马哈扑克手牌中所有可能的棋牌组合。是的，还有其他方法可以解决这个问题，但我正在测试这种方法，因为处理位比大多数其他选择要快得多。

Answer 1

嗯，我知道了。我认为。我为我不完全确定的碎片字段构建了一个Gosper's Hack版本，但它适用于这种情况。

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;
}

我不确定为什么标有星号的行中的 2 是 2 而不是 1。

无论如何，如果你在循环中x = next(x, 0x155)(当然从x = 0x15开始(，你会得到你列出的十件事。

Answer 2

我还尝试调整标准算法来枚举一组完整位的组合。该算法找到最低的 1 位组，将最高的位向左移动，并将其他位移动到底部。因此，对于我们的情况，我们需要找到 k 个最低设置位。我不知道如何在没有循环的情况下做到这一点，它假设有一个快速的"popcount"指令可用(计算 1 位的数量(：

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;
}

编辑：我在国际象棋编程维基上发现了一种不同的方法，该方法没有popcount：遍历集合的子集。可以稍微简化如下：

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;
}

由于循环平均只执行一次，这在我的机器上似乎略快，可能也是因为 popcount 的延迟不好。

Answer 3

这里有一些快速的解决方案。

构造数组

public static final long[] toThreeBitCombinations(long e) {
    //   get lowest 1 bit; turn off that bit;
    final long a = e & -e; e ^= a;
    final long b = e & -e; e ^= b;
    final long c = e & -e; e ^= c;
    final long d = e & -e; e ^= d;
    final long ab = a | b;
    final long ae = a | e;
    final long be = b | e;
    final long cd = c | d;
    return new long[] { cd | e, be | d, ae | d, be | c, ae | c,
                        ab | e, b | cd, a | cd, ab | d, ab | c
                      };
}

此方法生成与示例输入所需的输出相同的输出。如果您希望数组按升序排列：

public static final long[] toThreeBitCombinations(long e) {
    //   get lowest 1 bit; turn off that bit;
    final long a = e & -e; e ^= a;
    final long b = e & -e; e ^= b;
    final long c = e & -e; e ^= c;
    final long d = e & -e; e ^= d;
    final long ab = a | b;
    final long ae = a | e;
    final long be = b | e;
    final long cd = c | d;
    return new long[] { ab | c, ab | d, a | cd, b | cd, ab | e,
                        ae | c, be | c, ae | d, be | d, cd | e
                      };
}

可以看出，顺序是相反的。

对于整个数组的构造，我们有：

铝的使用

• 4 &
• 14 |
• 4 ^
• 4 一元-

可变内存使用情况

• 最多 10 个 64 位long同时活动

方法调用

• 每个元素调用此方法的 1/10

与此处介绍的其他解决方案相比，整个阵列的 26 条 ALU 指令、使用的 80 个字节和 1 个方法调用具有优势。它也不需要额外的工作来弄清楚用什么三位值的组合来启动这些循环。

判断元素是否在数组中，而无需构造数组

这通常比构造一个十元素数组并对其使用线性搜索要慢，除非您在构造数组后非常快速地丢弃数组。

public static final boolean inThreeBitCombinations(final long three, final long five) {
    return ((three & ~five) == 0) && (Long.bitCount(three) == 3);
}