我如何找到所有正好有6个1和其余0的32位二进制数

Question

我可以用蛮力做到这一点，但是我希望有聪明的编码，或者是现有的功能，或者我没有意识到的东西...

所以我想要一些数字的例子：

00000000001111110000
11111100000000000000
01010101010100000000
10101010101000000000
00100100100100100100

完整排列。除非结果只有六个1。不多。不低于。64或32位将是理想的。16位（如果提供答案）。

Answer 1

好吧，我不是 Python 编码员，所以我无法为您发布有效的代码。相反，我可以做一个C++ ......

如果你看看你的问题，你设置了 6 位和许多零......所以我会通过 6 个嵌套 for 循环计算所有可能的1s位置并设置位来解决这个问题......

就像是：

 for (i0=   0;i0<32-5;i0++)
  for (i1=i0+1;i1<32-4;i1++)
   for (i2=i1+1;i2<32-3;i2++)
    for (i3=i2+1;i3<32-2;i3++)
     for (i4=i3+1;i4<32-1;i4++)
      for (i5=i4+1;i5<32-0;i5++)
       // here i0,...,i5 marks the set bits positions

因此，O(2^32)变得小于 `~O(26.25.24.23.22.21/16) 并且你不能比这更快，因为这意味着你会错过有效的解决方案......

我假设您想打印数字，因此为了加快速度，您可以从一开始就将数字计算为二进制数字字符串，以避免字符串和数字之间的缓慢转换...

嵌套的 for 循环可以编码为数组的增量操作（类似于 bignum 算术）

当我把所有的东西放在一起时，我得到了这个C++代码：

int generate()
    {
    const int n1=6;     // number of set bits
    const int n=32;     // number of bits
    char x[n+2]; // output number string
    int i[n1],j,cnt; // nested for loops iterator variables and found solutions count
    for (j=0;j<n;j++) x[j]='0'; x[j]='b'; j++; x[j]=0;  // x = 0
    for (j=0;j<n1;j++){ i[j]=j; x[i[j]]='1'; } // first solution
    for (cnt=0;;)
        {
//      Form1->mm_log->Lines->Add(x);   // here x is the valid answer to print
        cnt++;
        for (j=n1-1;j>=0;j--) // this emulates n1 nested for loops
            {
            x[i[j]]='0'; i[j]++;
            if (i[j]<n-n1+j+1){ x[i[j]]='1'; break; }
            }
        if (j<0) break;
        for (j++;j<n1;j++){ i[j]=i[j-1]+1; x[i[j]]='1'; }
        }
    return cnt;         // found valid answers
    };

当我使用它时，n1=6,n=32我得到了这个输出（不打印数字）：

cnt = 906192

它是在4.246 msAMD A8-5500 3.2GHz（win7 x64 32 位应用程序无线程）上完成的，这对我来说足够快了......

请注意，一旦开始在某个地方输出数字，速度就会急剧下降。特别是如果你输出到控制台或其他什么......最好以某种方式缓冲输出，例如一次输出 1024 个字符串数字等......但正如我之前提到的，我不是 Python 编码员，所以它可能已经由环境...

最重要的是，一旦您使用变量，n1,n您可以对零而不是一执行相同的操作，并使用更快的方法（如果零较少，则使用嵌套 for 循环来标记零而不是一）

如果想要的解决方案编号需要作为数字（而不是字符串），那么可以重写它，以便i[]ori0,..i5保存位掩码而不是位位置...而不是 inc/dec，您只需左移/右移...而不是不再需要x数组，因为数字是x = i0|...|i5......