创建具有特定位数的多个数字

Question

问题

我需要创建32位数字(有符号或无符号无关紧要,最高位永远不会被设置),每个数字必须设置给定的位数.

天真的解决方案

最简单的解决方案当然是从零开始.在循环内,数字现在增加1,计数位数,如果计数具有所需值,则数字存储到列表中,否则循环重复.如果找到足够的数字,则停止循环.当然这很好用,但是一旦所需位数变得非常高,它就会非常慢.

更好的解决方案

具有(比方说)5位的最简单的数字是设置前5位的数字.这个号码可以很容易地创建.在循环内,第一个位置位,数字向左移一个.这个循环运行5次,我找到第一个设置了5位的数字.接下来的几个数字也很容易创建.我们现在假装数字为6位宽,最高位数未设置.现在我们开始将第一个零位向右移动,因此我们得到101111,110111,111011,111101,1111110.我们可以通过在前面添加另一个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范围内的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位数字显然很容易.