/*   bitsort.c   --   bitmap   sort   from   Column   1      *       Sort   distinct   integers   in   the   range   [0..N-1]      */       #include   <stdio.h>       #define   BITSPERWORD             32         //   定义每个int类型可以容纳32位   #define   SHIFT                   5          //   32=2^5   #define   MASK                    0x1F       //   5位的屏蔽  #define   N                       10000000   //   位数组总共有多少位    int   a[1 + N/BITSPERWORD];                  //   位数组用int数组来实现       void   set(int   i){ a[i>>SHIFT] |= (1<<(i & MASK));  }  //置1第i位           /*  提取数组当中的第i位              因为每个int容纳32位，   i/32的整数部分就是在int数组当中哪个元素里面，位移替代除法              i/32的余数部分就是int数组当中相应元素对应的位数              比如   i＝61，   那么   i/32   =   1   表示在a[1]元素当中              i＝61，   i/32的余数是29＝i&mask,   表示在a[1]元素的第29位保存               */  void   clr(int   i){ a[i>>SHIFT] &=  ~(1<<(i & MASK)); }  //清0第i位    int    test(int  i){ return  a[i>>SHIFT] & (1<<(i & MASK)); }  //提取第i位的值      int   main()   {                 int   i;                  for   (i   =   0;   i   <   N;   i++)                  clr(i);  //   把数组每一位都设置为0                  // 因为逐位操作效率不高，可以用下面的三行对整型数组赋值的方式取代                   /* Replace   above   2   lines   with   below   3   for   word-parallel   init                  int   top   =   1   +   N/BITSPERWORD;                  for   (i   =   0;   i   <   top;   i++)                  a[i]   =   0;                  */                  while   (scanf("%d",   &i)   !=   EOF)  //   根据输入的数值，设置对应的位                     set(i);                                     for   (i   =   0;   i   <   N;   i++)   //   检测哪一位是1                      if   (test(i))                        printf("%d ",   i);    return   0;    }   

 1 # Python implementation of bitsort algorithm from "Programming Pearls" 2 #http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/528942 3  4 def bitsort(filename, maxn): 5     """ Sort a file named ‘filename‘ which 6     consists of maxn integers where each 7     integer is less than maxn """ 8  9     # Initialize bitmap10     a = [0]*maxn11 12     # Read from file and fill bitmap13     for line in file(filename):14         n = int(line.strip())15         # Turn bits on for numbers16         if n<maxn: a[n] = 117 18     # Return a generator that iterates over the list19     for n in range(len(a)):20         if a[n]==1: yield n21 22     23 if __name__=="__main__":24     # numbers.txt should contain a list of numbers25     # each less than 1000000, one per line.26     for num in bitsort(‘numbers.txt‘,1000000):27         print num