Efficient enumeration of all integers with a given pop count

Population count is the number of '1' bits in the binary representation of an integer.

The basic trick we employ is to get the next higher number with the same number of 1-bits, which we borrow from the Hacker's Delight (whole book). Below is a Java implementation of all 4 version of the snoob function.

public static int snoob1(int x) {
    int r = x + (x & -x);
    return r | ((x ^ r) >>> (2 + Integer.numberOfTrailingZeros(x)));
}

public static int snoob2(int x) {
    int s = x & -x, r = x + s;
    return r | ((x ^ r) >>> (33 - Integer.numberOfLeadingZeros(s)));
}

public static int snoob3(int x) {
    int r = x + (x & -x);
    return r | ((1 << (Integer.bitCount(x ^ r) - 2)) - 1);
}

public static int snoob4(int x) {
    int s = x & -x, r = x + s;
    return r | (((x ^ r) >> 2) / s);
}

We utlize this formula to implement the method below, where the width parameter is added for convenience.

public static void printAllIntegersOfWidthAndPop(int w, int n) {
    if (n <= 0 || n > w || w > 32) return;
    int x = (1 << n) - 1, g = x << (w - n), c = 0;
    while (true) {
        String s = Integer.toBinaryString(x);
        while(s.length() < w) s = "0" + s;
        System.out.println(++c + "\t" + s);
        if (x == g) break;
        else x = snoob*(x);
    }
}

It is easy to figure out there will be Choose(w, n) such numbers. We know where the sequence starts and since we also know where it stops, we don't need to compute this number.

If you'd like to learn how to find the number of leading/trailing zeros or the pop count or learn about more cool bit twiddling hacks you can consult the book above (which the java.lang.Integer implementation of these methods is based on) or this magnificent web page.