创建多个数字与一定数量的设置位 [英] Creating multiple numbers with certain number of bits set

问题描述

我需要建立32位数字（符号或无符号无所谓，最高位将永远不会被无论如何设置），并且每个数必须有位给定数量的设置。

I need to create 32 Bit numbers (signed or unsigned doesn't matter, the highest bit will never be set anyway) and each number must have a given number of Bits set.

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

The easiest solution is of course to start with the number of zero. Within a loop the number is now increased by one, the number of Bits is counted, if the count has the desired value, the number is stored to a list, if not the loop just repeats. The loop is stopped if enough numbers have been found. Of course this works just fine, but it's awfully slow once the number of desired Bits gets very high.

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

The simplest number having (let's say) 5 Bits set is the number where the first 5 Bit are set. This number can be easily created. Within a loop the first bit is set and the number is shifted to the left by one. This loop runs 5 times and I found the first number with 5 Bits set. The next couple of numbers are easy to create as well. We now pretend the number to be 6 Bit wide and the highest one is not set. Now we start shifting the first zero bit to the right, so we get 101111, 110111, 111011, 111101, 111110. We could repeat this by adding another 0 to front and repeating this process. 0111110, 1011110, 1101110, etc. However that way numbers will grow much faster than necessary, as using this simple approach we leave out numbers like 1010111.

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

So is there a better way to create all possible permutations, a generic approach, that can be used, regardless how many bits the next number will have and regardless how many set bits we need set?

推荐答案

您可以使用该位twiddeling黑客从hackersdelight.org。

You can use the bit-twiddeling hack from hackersdelight.org.

在他的书中，他有code，以获得下一个更高的数字与一位集数相同。

In his book he has code to get the next higher number with the same number of one-bit set.

如果您使用此作为一种原始的，以增加你的电话号码所有你需要做的是找到一个出发点。获得与N位设置的第一个数字是容易的。这只是2 ^（N-1）-1。

If you use this as a primitive to increase your number all you have to do is to find a starting point. Getting the first number with N bits set is easy. It's just 2^(N-1) -1.

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

You will iterate through all possible numbers very fast that way.

  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 start = 3; // pick a number with two bits set..
    int i;

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

在code（和绝招其他变体）可以在这里找到：

The code (and other variations of the trick) can be found here:

http://hackersdelight.org/HD$c$c/snoob.c

这篇关于创建多个数字与一定数量的设置位的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！