有一定数量的位集创建多个号码

Question

问题

我需要创建32位数字（符号或无符号不要紧，最高位不会被设置无论如何），每个号码必须有位给定数目的设置。

幼稚解决方案

的最简单的解决方案是当然的开始与零的数目。在循环中，现在的数量增加了一个，位的数量进行计数，如果计数具有所期望的值，号码存储到一个列表中，如果不是循环重复刚。如果有足够的数量已被发现的循环停止。当然，这工作得很好，但它是非常缓慢，一旦所需位的数量变得非常高。

更好的解决方案

具有最简单的数目（比方说）5位设置是第一5位被设置的数量。这个数字可以轻松创建。在循环中第一位被置数由一个左移。这个循环运行5次，我发现有5位设置第一个数字。在接下来的几个数字很容易创建为好。现在，我们假装数为6位宽，最高的一个未设置。现在我们开始第一个零位右移，所以我们得到101111，110111，111011，111101，111110.我们可以通过添加另外一个0到前面，重复此过程重复这一点。 0111110，1011110，1101110等，但这样的数字增长将超过必要的快得多，因为使用这种简单的方法，我们离开了号码，如1010111。

那么，有没有更好的方式来创造所有可能的排列，一个通用的方法，可以使用，不管下一个数字将有多少位有且不论我们需要多少集位设置？

Answer 1

可以使用位变换从hackersdelight.org 劈。

在他的书中，他有代码来获取下一个更高的数字有相同数量的一个位集。

如果您使用此作为一种原始的，以增加你的电话号码，所有您需要做的是找到一个起点。掌握设定N位的第一数目是容易的。它只是2 ^（N-1）-1。

您将通过所有可能的数字迭代速度非常快的方式。

  unsigned next_set_of_n_elements(unsigned x) 
  {
     unsigned smallest, ripple, new_smallest, ones;

     if (x == 0) return 0;
     smallest     = (x & -x);
     ripple       = x + smallest;
     new_smallest = (ripple & -ripple);
     ones         = ((new_smallest/smallest) >> 1) - 1;
     return ripple | ones;
  }

  // test code (shown for two-bit digits)

  void test (void)
  {
    int bits = 2;
    int a = pow(2,bits) - 1;
    int i;

    for (i=0; i<100; i++)
    {
       printf ("next number is %d\n", a);
       a = next_set_of_n_elements(a);
    }
  }

Answer 2

尝试从轮相反的方向接近的问题 - 你想做什么就相当于“找到的名词的范围为0-31号”

假设你正在试图找到4个号码。你开始[0,1,2,3]，然后每次（得到[0,1,2,4]，[0,1,2,5] ...），直到你打了极限提高的最后一个号码[0,1,2,31]。然后提高倒数第二个号码，最后数设定为一更高：[0,1,3,4]。回到增长的最后一个号码：[0,1,3,5]，[0,1,3,6] ...等，一旦你打这个月底，你回去[0,1,4 5] - 最终到达[0,1,30,31]在这一点你必须原路返回一步：[0,2,3,4]和关闭你又来了。一直走，直到你最后用[28,29,30,31]结束了。

给定一组数字，这显然容易将它们转换成32位数字。

Answer 3

您想生成的组合，看到这个维基百科的文章。

Answer 4

您要么需要Factoradic排列组合（谷歌上）或在维基