20

问题

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

天真的解决方案

最简单的解决方案当然是从零开始。在一个循环内，数字现在增加一，对位的数量进行计数，如果计数具有所需的值，则将数字存储到列表中，如果不是，则循环重复。如果找到足够的数字，则停止循环。当然，这工作得很好，但是一旦所需的位数变得非常高，它就会非常慢。

更好的解决方案

设置（假设）5 位的最简单数字是设置前 5 位的数字。这个号码可以很容易地创建。在一个循环中，第一位被设置并且数字向左移动一个。这个循环运行了 5 次，我找到了第一个设置了 5 位的数字。接下来的几个数字也很容易创建。我们现在假设这个数字是 6 位宽，并且最高的没有设置。现在我们开始将第一个零位向右移动，因此我们得到 101111、110111、111011、111101、111110。我们可以通过在前面添加另一个 0 并重复此过程来重复此过程。0111110、1011110、1101110 等。然而，这样数字的增长速度会比必要的快得多，因为使用这种简单的方法，我们会忽略像 1010111 这样的数字。

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

4

4 回答 4

17

您可以使用来自hackersdelight.org 的bit-twiddling hack。

在他的书中，他有代码可以使用相同数量的一位集合来获得下一个更高的数字。

如果您将其用作增加数量的原语，您所要做的就是找到一个起点。获得设置了 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);
    }
  }
于 2009-02-03T12:11:18.340 回答
15

尝试从相反的方式解决问题 - 您尝试做的相当于“在 0-31 范围内查找n 个数字”。

假设您要查找 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 位数字。

于 2009-02-03T12:05:06.933 回答
1

您想生成组合，请参阅此Wikipedia 文章。

于 2009-02-03T12:18:30.900 回答
0

您要么需要 Factoradic Permutations (Google on that)，要么需要 Wiki 上的一种算法

于 2009-02-03T11:54:05.677 回答