思考题1的java实现。
import java.util.Random;

public class BitMap {
    private int[] bits;
    private int[] input;

    public BitMap(int n, int[] input) {
        bits = new int[n];
        this.input = input;
    }

    public void setBit(int n) {
        int offset = n / 32;
        int value = n % 32;
        bits[offset] |= (1 << value);
    }

    public boolean getBit(int n) {
        int offset = n / 32;
        int value = n % 32;
        return (bits[offset] & (1 << value)) != 0;
    }

    /**
     * 排序
     *
     * @param n
     * 是数组的存储整数范围
     * @param input
     * 输入的未排序数组
     * @return 有序的数组范围
     */
    public int sort(int n, int[] input) {
        int j = 0;
        for (int i = 1; i <= 10 * n; i++) {
            if (getBit(i)) {
                input[j++] = i;
            }
        }
        return j;
    }

    public static void main(String[] args) {
        int n = 1000000000;
        int[] input = new int[n];
        Random r = new Random();
        for (int i = 0; i < n; i++) {
            input[i] = r.nextInt(10 * n - 1) + 1;
        }
        BitMap bitMap = new BitMap(10 * n, input);
        for (int i = 0; i < n; i++) {
            bitMap.setBit(input[i]);
        }
        int size = bitMap.sort(n, input);
        for (int i = 0; i < size; i++)
            System.out.print(input[i] + ",");
    }
}