查找设置了某些位的long的所有组合

这是一个非常模糊的问题，我怀疑我必须在我的代码中以不同的级别进行…但希望Stack Overflow的蜂巢思维可以帮助……

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

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

可以看出，订单是相反的 。

我们有，用于构建整个arrays：

ALU用法

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

可变内存使用

• 最多可同时存在10个64位long s

方法调用

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

对于整个arrays，26个ALU指令，80个字节和1个方法调用与此处提供的其他解决方案相比具有优势。 它也不需要额外的工作来确定什么组合的三位值来启动这些循环。

如果元素在数组中而不需要构造数组，则告诉它

这通常比构造一个十元素数组并在其上使用线性搜索要慢，除非你在构造它们之后很快就会破坏数组。

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