这篇文章简直就是位操作的练习，各种位操作都使用到了。
主要思想是将n选m表示为一个长度为n的二进制串，1为选中，0为不选中。每次的结果都根据上一次生成的结果在常数时间生成的，即从右向左查找第一个01，将其变为10，并把这个位置往右的的1都推向最右边。初始的字符串1都在最右边，最后终止的时候1都在左边。
代码如下，比较难懂。
1 #include <stdio.h> 2 #include <malloc.h> 3 //这篇代码的适用范围是64位以内的组合问题，即0的个数与1的个数不超过64.虽然写代码的时候我只用32位，即int，为了偷懒。。。 4 //每一个新的组合跟上一个的组合都是有关联的，即从右向左找第一个序列为01的对，然后将他变成10,并将这个01后面的1全都移到最右端，然后就生成了新的组合。 5 //而且组合的生成序列是按照词法序的，每生成一个序列所需要的时间为常数 6 #define ZERO 7 7 #define ONES 3 8 unsigned int countbits(unsigned int input)//得到一个二进制串中1的个数 9 { 10 unsigned int bits_counter = 0; 11 bits_counter = input; 12 bits_counter = (bits_counter & 0x55555555) + ((bits_counter >> 1) & 0x55555555); 13 bits_counter = (bits_counter & 0x33333333) + ((bits_counter >> 2) & 0x33333333); 14 bits_counter = (bits_counter & 0x0f0f0f0f) + ((bits_counter >> 4) & 0x0f0f0f0f); 15 bits_counter = (bits_counter & 0x00ff00ff) + ((bits_counter >> 8) & 0x00ff00ff); 16 bits_counter = (bits_counter & 0x0000ffff) + ((bits_counter >> 16) & 0x0000ffff); 17 return bits_counter; 18 } 19 void outprint(unsigned int input) 20 { 21 unsigned int bit_count = 1<<31; 22 while (bit_count >= 1) 23 { 24 printf("%d ", (bit_count&input) && 1); 25 bit_count = bit_count >> 1; 26 } 27 printf(" "); 28 } 29 int main() 30 { 31 unsigned int output; 32 unsigned int part,next,temp1,temp2,end,bit_count_1,bit_count_2; 33 int count = 0; 34 output =( 1 << (ONES) )-1;//initial 35 end = output << ZERO; 36 while (output != end)//这里以例子0101100000来说明 37 { 38 outprint(output); 39 count++; 40 part = (output - 1) ^ output;//这里首先获得output 0101100000的最后的连续的0，当末尾是100000时，我们将会得到111111 41 bit_count_1 = countbits(part)-1;//通过这一步我们得到了output末尾0的个数 这里为5 42 next = part | output;//通过这步，我们把output末尾的连续的0都变成了1，0101100000会变成0101111111 43 temp1 = (next + 1) ^ next;//通过这一步，我们把end 0101111111变成了0011111111，即把output从右往左数第一个以01为前缀的后缀全都变成了1 44 bit_count_2 = countbits(temp1) - 2;//通过这一步，我们得到了从右往左数第一个01 中的1的后面的位数，这里为6 45 bit_count_2 = bit_count_2 - bit_count_1;//这样我们就得到了01后面1的个数 这里为1 46 temp2 = temp1 - (temp1>>1);//通过这一步我们把temp1的第二个1及以后的所有位变成了0得到了0010000000 47 temp2 = temp2 | ((1 << bit_count_2) - 1);//将这个01后面的1都放到最右边去，生成新的后缀0010000000变成了0010000001 48 output = output&(~temp1);//通过这一步，我们把output第一个01及以后的数全都清0，output变成了0100000000 49 output = output | temp2;//然后将两端组合起来，最后得到了0110000001 50 51 } 52 outprint(output); 53 count++; 54 printf("%d ", count); 55 }