位掩码生成以最小化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未定义......

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:A参考手册,第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,就应该没有问题.