N-bit x containing L 1s

Question

Are there any fast algorithms that can store all the different N-bit numbers containing L bits 1 s? With the provided parameters N and L. This is in order to crack the cryptosystem in the class, and I noticed that with two instant attacks I can find out the bit length (N) and the number 1 bit (L).

Instead of rudely forcing all values ​​between the lower and upper limits, I would rather minimize the elements I need to check. Therefore, I was thinking about the presence of a vector containing all the elements that he could pick up for the information I received from two time attacks.

Any advice at all would be appreciated.

I am using C ++.

Answer 1

Page Bit Tweedling Hacks shows how to enumerate all binary number with exactly n bits, installed using O (1) work in the number of generated numbers. Their solution is reprinted here:

Suppose we have a pattern of N bits set to 1 in an integer, and we want the next permutation of N 1 bits in the lexicographic sense. For example, if N is 3 and the bit-bit is 00010011, the following patterns will be 00010101, 00010110, 00011001,00011010, 00011100, 00100011, and so on. The following is a quick way to calculate the next permutation.

unsigned int v; // current permutation of bits
unsigned int w; // next permutation of bits

unsigned int t = v | (v - 1); // t gets v least significant 0 bits set to 1

// Next set to 1 the most significant bit to change,
// set to 0 the least significant ones, and add the necessary 1 bits.
w = (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctz(v) + 1));

__builtin_ctz(v) GNU C, x86, . Microsoft x86, _BitScanForward. bsf . , , . , - , .

unsigned int t = (v | (v - 1)) + 1;
w = t | ((((t & -t) / (v & -v)) >> 1) - 1);

0, L , 1, , .

, !

Answer 2

... templatetypedef , , , . . , , , , , ( : !).

, , , . , , . , , / ! , , . , .

#include <bitset>
#include <vector>
using namespace std;

const int N = 4;

void addValues(int to_add, int start_pos, bitset<N> const& working, vector<bitset<N>>& values)
{
  // Take all of our possible spots
  for (int i = start_pos; i < N && i <= N - to_add; ++i) {
    auto working_copy(working);
    working_copy[i] = 1;

    // We have more bits to set...
    if (to_add > 1) {
      addValues(to_add - 1, i + 1, working_copy, values);
    } 
    // We've set all the bits, so this is a working combination
    else {
      values.push_back(working_copy);
    }
  }
}

int main(int argc, char* argv)
{
  int L = 2;

  vector<bitset<N>> values;
  bitset<N> working;
  addValues(L, 0, working, values);

  return EXIT_SUCCESS;
}