位掩码生成以最小化1的数量

Question

为了探索一些解决方案，我需要生成所有可能性。我通过使用位掩码来实现，就像这样：

for (long i = 0; i < 1L << NB; i++) {
    System.out.println(Long.toBinaryString(i));
    if(checkSolution(i)) {
        this.add(i); // add i to solutions
    }
}
this.getBest(); // get the solution with lowest number of 1

这让我有机会探索（如果NB=3）：

000
001
010
011
100
101
110
111

我的问题是最佳解决方案是1的数量最少的解决方案。因此，为了在找到解决方案后尽快停止搜索，我希望有一个不同的顺序，并产生类似于这样的结果:

000
001
010
100
011
101
110
111

如果我能在获得第一个解决方案后停止搜索，那么搜索速度将会更快。但是我不知道如何更改循环以获得这个输出...

PS：NB未定义...

- ncenerar

---

@FilipeGonçalves：你是想告诉我们(0b011 + 1) > (1<<3)即4 > 8吗？ - fabian

@fabian 不用管了，我显然错了。我刚才把 1 << 3 当作 100 ，我的错误。 - Filipe Gonçalves

为什么要使用长整型？如果整数不足以满足需求，那么计算时间会非常长，因此我建议您使用整数。 - martijnn2008

@martijnn2008 掩码的大小可以是60，但只包含3个位设置为1的解决方案。在这种情况下，我需要一个长整型来表示掩码，并且我需要对我的搜索进行排序，以便更快地找到此解决方案。确定掩码中1的数量的上限是另一回事 ;) - ncenerar

Answer 1

这个想法是将你的循环转化为两个嵌套循环；外层循环设置1的数量，内层循环迭代每个具有N个1的二进制数的组合。因此，你的循环变成了：

for (long i = 1; i < (1L << NB); i = (i << 1) | 1) {
  long j = i;
  do {
    System.out.println(Long.toBinaryString(j));
    if(checkSolution(j)) {
        this.add(j); // add j to solutions
    }
    j = next_of_n(j);
  } while (j < (1L << NB));
}

next_of_n()的定义如下:

long next_of_n(long j) {
  long smallest, ripple, new_smallest, ones;
  if (j == 0)
    return j;
  smallest = (j & -j);
  ripple = j + smallest;
  new_smallest = (ripple & -ripple);
  ones = ((new_smallest / smallest) >> 1) - 1;
  return (ripple | ones);
}

next_of_n()算法的实现在《C语言参考手册，第5版》7.6节中有所描述，并展示了一种使用位运算实现SET的例子。一开始可能很难理解代码，但是这本书对其有如下解释：

这段代码利用了无符号算术运算的许多不寻常特性，以下是一个例子：

if x ==               001011001111000, then

smallest ==           000000000001000
ripple ==             001011010000000
new_smallest ==       000000010000000
ones ==               000000000000111
the returned value == 001011010000111

整体思路是找到最右边的连续一组1位。在该组中，将最左边的1位向左移动一个位置，并将所有其他位移到极右侧。(此代码改编自HAKMEM)。如果您仍不理解，我可以提供更深入的解释。请注意，该算法假定2补数，并且所有算术运算最好在无符号整数上进行，主要是因为右移操作。我不是一个非常熟悉Java的人，在C中使用unsigned long测试这个算法效果很好。我希望在Java中也适用，尽管Java中没有unsigned long这样的类型。只要对NB使用合理的值，就不应该有问题。

- Filipe Gonçalves

---

Java 中没有无符号类型。如果需要 32 位无符号类型，必须使用 64 位的 long 类型进行“模拟”，并在必要时添加掩码。这是 Java 中非常令人烦恼的一个方面。 - Gene

@Gene Yep，我知道。这真是让人头疼。这就是为什么我说希望它在Java中能够工作。但我认为只要“NB”是一个合理的值，即不会触碰符号位的值，那么这应该不是问题。 - Filipe Gonçalves

这个算法和这个是一样的吗？ - OldCurmudgeon

@OldCurmudgeon 对我来说看起来一样，只是稍微更加模糊:p - Filipe Gonçalves

@Gene，你不需要模拟任何东西，Java使用二进制补码，这意味着对于任何有符号原始类型进行的基本操作（+、-、~、<<、>>>），都会产生与相应的无符号类型所产生的相同位模式。只有在使用关系运算符（>、>=、<、<=）时需要小心。对于这些运算符，将比较前的最高位翻转即可得到无符号结果。主要问题在于程序员方面不出错。 - Durandal

@Durandal 如果你想表示2^32-1，你必须使用long，如果你想表示2^8-1，你必须使用int。这就是我想说的全部内容。 - Gene

Answer 2

这是一个迭代器，可以迭代相同基数的位模式。

/**
 * Iterates all bit patterns containing the specified number of bits.
 *
 * See "Compute the lexicographically next bit permutation"
 * http://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation
 *
 * @author OldCurmudgeon
 */
public class BitPattern implements Iterable<BigInteger> {
  // Useful stuff.
  private static final BigInteger ONE = BigInteger.ONE;
  private static final BigInteger TWO = ONE.add(ONE);
  // How many bits to work with.
  private final int bits;
  // Value to stop at. 2^max_bits.
  private final BigInteger stop;
  // Should we invert the output.
  private final boolean not;

  // All patterns of that many bits up to the specified number of bits - invberting if required.
  public BitPattern(int bits, int max, boolean not) {
    this.bits = bits;
    this.stop = TWO.pow(max);
    this.not = not;
  }

  // All patterns of that many bits up to the specified number of bits.
  public BitPattern(int bits, int max) {
    this(bits, max, false);
  }

  @Override
  public Iterator<BigInteger> iterator() {
    return new BitPatternIterator();
  }

  /*
   * From the link:
   * 
   * Suppose we have a pattern of N bits set to 1 in an integer and 
   * we want the next permutation of N 1 bits in a lexicographical sense. 
   * 
   * For example, if N is 3 and the bit pattern is 00010011, the next patterns would be 
   * 00010101, 00010110, 00011001,
   * 00011010, 00011100, 00100011, 
   * and so forth. 
   * 
   * The following is a fast way to compute the next permutation. 
   */
  private class BitPatternIterator implements Iterator<BigInteger> {
    // Next to deliver - initially 2^n - 1
    BigInteger next = TWO.pow(bits).subtract(ONE);
    // The last one we delivered.
    BigInteger last;

    @Override
    public boolean hasNext() {
      if (next == null) {
        // Next one!
        // t gets v's least significant 0 bits set to 1
        // unsigned int t = v | (v - 1); 
        BigInteger t = last.or(last.subtract(BigInteger.ONE));
        // Silly optimisation.
        BigInteger notT = t.not();
        // Next set to 1 the most significant bit to change, 
        // set to 0 the least significant ones, and add the necessary 1 bits.
        // w = (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctz(v) + 1));
        // The __builtin_ctz(v) GNU C compiler intrinsic for x86 CPUs returns the number of trailing zeros.
        next = t.add(ONE).or(notT.and(notT.negate()).subtract(ONE).shiftRight(last.getLowestSetBit() + 1));
        if (next.compareTo(stop) >= 0) {
          // Dont go there.
          next = null;
        }
      }
      return next != null;
    }

    @Override
    public BigInteger next() {
      last = hasNext() ? next : null;
      next = null;
      return not ? last.not(): last;
    }

    @Override
    public void remove() {
      throw new UnsupportedOperationException("Not supported.");
    }

    @Override
    public String toString () {
      return next != null ? next.toString(2) : last != null ? last.toString(2): "";
    }

  }

  public static void main(String[] args) {
    System.out.println("BitPattern(3, 10)");
    for (BigInteger i : new BitPattern(3, 10)) {
      System.out.println(i.toString(2));
    }
  }

}

- OldCurmudgeon

---

我喜欢创建迭代器和使用BigInteger的原始想法！那很聪明。有一个问题：为什么你创建了一个私有类而不是将其作为public class BitPattern implements Iterable<BigInteger>, Iterator<BigInteger>？ - ncenerar

@ncenerar - 实现Iterable和Iterator两者都是不好的做法，因为Iterable.iterator()可能会被调用两次。这种方式也更简单。详细原因请参考这里。 - OldCurmudgeon

Answer 3

首先，您需要循环处理您的1的数量，例如n。首先，您从2^n-1开始，这是第一个包含恰好n个1的整数，并对其进行测试。要获取下一个整数，您可以使用基于汉明权重的索引算法（它是C代码，但应该不难将其翻译成Java）。

- Drunix

---

这是一个非常有用的答案！我找不到任何概念，你给了我“汉明重量”...那正是我需要查找的地方，谢谢！现在，我想找到一个更好的表述方式，以便任何寻找类似内容的人都能找到它...如果你有任何想法，请随时帮助我 ;) - ncenerar

将主题改为“按设置的位数递增枚举整数”如何？ - Drunix

Answer 4

这是我之前编写的一些代码，用于执行此操作。使用combinadic方法，给定所需位数、所需比特数和序列中的数字。

// n = digits, k = weight, m = position.
public static BigInteger combinadic(int n, int k, BigInteger m) {
    BigInteger out = BigInteger.ZERO;
    for (; n > 0; n--) {
        BigInteger y = nChooseK(n - 1, k);
        if (m.compareTo(y) >= 0) {
            m = m.subtract(y);
            out = out.setBit(n - 1);
            k -= 1;
        }
    }
    return out;
}

// Algorithm borrowed (and tweaked) from: https://dev59.com/UWUp5IYBdhLWcg3wY29V#15302448
public static BigInteger nChooseK(int n, int k) {
    if (k > n) {
        return BigInteger.ZERO;
    }
    if (k <= 0 || k == n) {
        return BigInteger.ONE;
    }
    // ( n * ( nChooseK(n-1,k-1) ) ) / k;
    return BigInteger.valueOf(n).multiply(nChooseK(n - 1, k - 1)).divide(BigInteger.valueOf(k));
}

public void test() {
    System.out.println("Hello");
    BigInteger m = BigInteger.ZERO;
    for ( int i = 1; i < 10; i++ ) {
        BigInteger c = combinadic(5, 2, m);
        System.out.println("c["+m+"] = "+c.toString(2));
        m = m.add(BigInteger.ONE);
    }
}

不确定它在效率方面与其他帖子相比如何匹配。

- OldCurmudgeon