3

这是一个如此晦涩难懂的问题，我怀疑我将不得不在我的代码中以不同的级别来做这件事……但希望 Stack Overflow 的蜂巢思维可以提供帮助……

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

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

我正在寻找一个包含所有十个可能的 long 的数组，其中恰好设置了三个位。继续这个例子，

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

以下是适当的方法签名可能的样子：

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

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

4

3 回答 3

2

嗯，我明白了。我认为。我为我不完全确定的零散字段构建了一个 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当然从开始）你会得到你列出的那十件事。

于 2013-09-28T18:02:15.403 回答
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;
}

编辑：我在国际象棋编程 wiki 中发现了一种没有 popcount 的不同方法：Traversing Subsets of a Set。可以稍微简化如下：

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 的延迟很差。

于 2015-03-13T22:43:43.993 回答
0

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

构造数组

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

可以看出，顺序颠倒了。

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

ALU 使用情况
  • 4&
  • 14|
  • 4^
  • 4 一元-
可变内存使用
  • long最多同时直播10 个 64 位
方法调用
  • 每个元素调用此方法的 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);
}
于 2018-08-01T14:54:13.267 回答