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.

Answer 2

This is an iterator that iterates bit patterns of the same cardinality.

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

}

Answer 3

First you loop over your number of ones, say n. First you start with 2^n-1, which is the first integer to contain exactly n ones and test it. To get the next one, you use the algorithm from Hamming weight based indexing (it's C code, but should not be to hard to translate it to java).

Answer 4

Here's some code I put together some time ago to do this. Use the combinadic method giving it the number of digits you want, the number of bits you want and which number in the sequence.

// 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: http://stackoverflow.com/a/15302448/823393
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);
    }
}

Not sure how it matches up in efficiency with the other posts.