创建具有特定位数设置的多个数字 [英] 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 位的数字.接下来的几个数字也很容易创建.我们现在假设这个数字是 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?

推荐答案

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

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

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 bits = 2;
    int a = pow(2,bits) - 1;
    int i;

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

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