Criando vários números com certo número de bits set

Question

Problema

Eu preciso criar 32 números de bits (com ou sem sinal não importa, o bit mais alto nunca vai ser definido de qualquer maneira) e cada número deve ter um determinado número de bits definidos.

Naive Solução

A solução mais fácil é, naturalmente, para começar com o número de zero. Dentro de um loop o número é agora aumentado por um, o número de bits é contado, se a contagem tem o valor desejado, o número é armazenado a uma lista, se não o loop apenas repete. O ciclo é interrompido se os números suficientes foram encontrados. Claro que isso funciona muito bem, mas é muito lento uma vez que o número de bits desejados fica muito alta.

A melhor solução

O número mais simples ter (digamos de LET) 5 Bits conjunto é o número onde a primeira 5 Bit está definido. Este número pode ser facilmente criados. Dentro de um loop o primeiro bit é definido e o número é deslocado para a esquerda por um. Este loop é executado 5 vezes e eu achei o primeiro número com 5 Bits set. O próximo par de números são fáceis de criar também. Nós agora fingir que o número seja 6 Bit de largura e o mais alto não está definido. Agora vamos começar a mudar o primeiro bit zero para a direita, então temos 101111, 110111, 111011, 111101, 111110. Poderíamos repetir isso adicionando outro 0 a frente e repetir este processo. 0111110, 1011110, 1101110, etc. No entanto que os números de forma irá crescer muito mais rápido do que o necessário, como usar essa abordagem simples que deixar de fora números como 1010111.

Então, há uma maneira melhor para criar todas as permutações possíveis, uma abordagem genérica, que pode ser usado, independentemente quantos bits o próximo número terá e independentemente quantos set pedaços Precisamos definir?

Answer 1

Você pode usar o href="http://hackersdelight.org/hdcodetxt/snoob.c.txt" rel="nofollow noreferrer"> Hack-girando pouco .

Em seu livro, ele tem o código para obter o número mais elevado seguinte com o mesmo número de série de um bit.

Se você usar isso como um primitivo para aumentar o seu número de tudo que você tem a fazer é encontrar um ponto de partida. Obtendo o primeiro número com N bits de conjunto é fácil. É apenas 2 ^ (N-1) -1.

Você vai percorrer todos os números possíveis muito rápido dessa forma.

  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

Tente abordar o problema do oposto maneira redonda -. O que você está tentando fazer é equivalente a "encontrar n números no intervalo 0-31"

Suponha que você está tentando encontrar 4 números. Você começa com [0,1,2,3] e, em seguida, aumentar o último número cada vez (recebendo [0,1,2,4], [0,1,2,5] ...) até atingir o limite [0,1,2,31]. Em seguida, aumentar o número penúltimo, e definir o último número a uma maior: [0,1,3,4]. Volte para aumentar o último número: [0,1,3,5], [0,1,3,6] ... etc. Depois de bater o final deste, você voltar para [0,1,4 , 5] - eventualmente você chegar [0,1,30,31] em que ponto você tem que recuar um passo além: [0,2,3,4] e temos que ir novamente. Continue indo até você finalmente acabar com [28,29,30,31].

Dado um conjunto de números, é, obviamente, fácil de convertê-los em números de 32 bits.

Answer 3

Você deseja gerar combinações, consulte este Wikipedia artigo .

Answer 4

Você nem precisa Factoradic permutações (Google sobre isso) ou um dos algoritmos na Wiki