Bit mask generation to minimize number of 1

Question

In order to explore some solutions, I need to generate all possibilities. I'm doing it by using bit masking, like this:

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

this allow me to explore (if NB=3):

000
001
010
011
100
101
110
111

My problem is that the best solution is the one with the lowest number of 1. So, in order to stop the search as soon as I found a solution, I would like to have a different order and produce something like this:

000
001
010
100
011
101
110
111

That would make the search a lot faster since I could stop as soon as I get the first solution. But I don't know how can I change my loop to get this output...

PS: NB is undefined...

Answer 1

The idea is to turn your loop into two nested loops; the outer loop sets the number of 1's, and the inner loop iterates through every combination of binary numbers with N 1's. Thus, your loop becomes:

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() is defined as:

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

The algorithm behind next_of_n() is described in C: A Reference Manual, 5th edition, section 7.6, while showing an example of a SET implementation using bitwise operations. It may be a little hard to understand the code at first, but here's what the book says about it:

This code exploits many unusual properties of unsigned arithmetic. As an illustration:

if x ==               001011001111000, then

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

The overall idea is that you find the rightmost contiguous group of 1-bits. Of that group, you slide the leftmost 1-bit to the left one place, and slide all the others back to the extreme right. (This code was adapted from HAKMEM.)

I can provide a deeper explanation if you still don't get it. Note that the algorithm assumes 2 complement, and that all arithmetic should ideally take place on unsigned integers, mainly because of the right shift operation. I'm not a huge Java guy, I tested this in C with unsigned long and it worked pretty well. I hope the same applies to Java, although there's no such thing as unsigned long in Java. As long as you use reasonable values for NB, there should be no problem.