Can anyone explain how this code generates combinations?

Question

I found some Java code for generating combinations on, but I can't understand what it is doing as it does some strange operations with bits.

import java.util.Collections;
import java.util.LinkedList;

public class Comb{

    public static void main(String[] args){
            System.out.println(comb(3,5));
    }

    public static String bitprint(int u){
            String s= "";
            for(int n= 0;u > 0;++n, u>>= 1)
                    if((u & 1) > 0) s+= n + " ";
            return s;
    }

    public static int bitcount(int u){
            int n;
            for(n= 0;u > 0;++n, u&= (u - 1));
            return n;
    }

    public static LinkedList<String> comb(int c, int n){
            LinkedList<String> s= new LinkedList<String>();
            for(int u= 0;u < 1 << n;u++)
                    if(bitcount(u) == c) s.push(bitprint(u));
            Collections.sort(s);
            return s;
    }
}

Answer 1

Given choose(r,n), it will create a number n bits wide, then count from 0 to 2^n. It checks each value to see if it has r bits set. If it does, it adds it as a valid combination. With these numbers, it forms valid combination strings.

There are much better algorithms for this. I suggest you search elsewhere.

Answer 2

A particular combination of a group of items can be represented as a binary number, where bit n of the number represents whether the combination includes item #n of the group.

The code is simply looping through enough binary numbers to represent a whole set of n items (from 0 to (1<<n) - 1, which is the same as 2^n-1), and adding every one that has exactly c 1-bits in it (meaning the items that'd be represented by those bits are in the given combo) to the list.