Блог

Это вопрос, отличный от того, который я только что задал, и он более сложный.

У меня есть массив символов без знака, скажем, unsigned char A[16] . Мне нужно сгенерировать вектор маски, который я применю к своему массиву A[16].

Он должен содержать n единиц, где 0 < n < 16 * 8 (вектор маски может быть массивом B[16], если в массиве n единиц)

Мне также нужно, чтобы эти n чисел ‘1 распределялись случайным образом в векторе.

Как я могу это сделать в c / c ?

Спасибо!

Редактировать: моя мысль заключается в следующем: я сгенерирую n случайных чисел (необходимо выполнить проверку, чтобы убедиться, что все n чисел не совпадают) и сохраню их в массиве tmp [n]. Затем маска генерируется на основе сдвига.

 srand(time(0));
for(i = 0; i < n; i  ){
  for(j = 0; j < i; j  ) 
    while(tmp[i] == tmp[j])  // to make sure all n random numbers are different
      tmp[i] = rand()%128;

unsigned char mask[16] 
for(i = 0; i < n; i  ) 
  mask[16] |= (1 << tmp[i]);  //generate mask
  

Сгенерировать случайную (i,j) пару чисел, где i < 16 и j < 8 . Если бит в позиции B[i]amp;(1<<j) не установлен, установите его и увеличьте «count». Цикл, пока «count» не достигнет «n».

Немного кода (непроверенный):

 void generate_n_bit_mask ( unsigned char B[], int n )
{
    // avoid infinite loop later on.
    for ( int i=0; (i < 16);   i ) {
        B[i] = 0;
    }
    // invariant: k is number of currently masked bits.
    for ( int k = 0; (k < n); )
    {
        // select bit at random.
        int i = rand() % 16;
        int j = rand() %  8;
        unsigned char mask = 1 << j;
        // set it if not selected previously.
        if ( (B[i]amp;mask) == 0 ) {
            B[i] |= mask,   k;
        }
    }
}
  

Упражнение для задачи: удалите магическую константу 16 из кода.

Редактировать: модификация, предложенная в ваших комментариях, содержит неприятную ошибку. Вот тестовая программа, позволяющая воспроизвести способ распределения битов в вашей выходной маске.

 #include <iostream>
#include <iomanip>
#include <ctime>

void generate_n_bit_mask ( unsigned char B[], int n )
{
    // avoid infinite loop later on.
    for ( int i=0; (i < 16);   i ) {
        B[i] = 0;
    }
    // invariant: k is number of currently masked bits.
    for ( int k = 0; (k < n); )
    {
        // select bit at random.
        int i = std::rand() % 16;
        int j = std::rand() %  8;
        unsigned char mask = 1 << j;
        // set it if not selected previously.
        if ( (B[i]amp;mask) == 0 ) {
            B[i] |= mask,   k;
        }
    }
    int j = 0;
}

// count number of set bits in a byte.
int bit_count ( unsigned char x )
{
    int n = 0;
    for ( int i = 0; (i < 8);   i ) {
        n  = ((x >> i) amp; 1);
    }
    return (n);
}

// count number of set bits in 16 bytes.
int total_bit_count ( unsigned char B[] )
{
    int n = 0;
    for ( int i = 0; (i < 16);   i ) {
        n  = bit_count(B[i]);
    }
    return (n);
}

int main ( int, char ** )
{
    std::srand(std::time(0));
    unsigned char B[16];
    // for all possible values of "n"
    for ( int i = 0; (i <= 16*8);   i )
    {
        // generate a 16 byte mask with "n" set bits.
        generate_n_bit_mask(B, i);
        // verify that "n" bits are set.
        int n = total_bit_count(B);
        if ( n != i ) {
            std::cout << i << ": " << n << std::endl;
        }
    }
}
  

Когда эта программа запускается, она пробует каждое значение n from 0 to 16*8 и генерирует случайную маску с n битами, затем проверяет, установлены ли именно n биты. Если возникает какая-либо ошибка (для некоторого значения n установлено несколько k!=n битов), выводится сообщение.

Если я изменю условие на if ( (B[i]^mask) != 0 ) , я получу последовательные ошибки в выходных данных. Каждый запуск выдает как минимум 1 сообщение об ошибке. Исходное условие if ( (B[i]amp;mask) == 0 ) последовательно выдает 0 сообщений об ошибках.

У вас есть массив из 16 unsigned char секунд, который можно рассматривать как 16 * 8 бит. Чтобы сгенерировать случайную маску с n 1 битами в ней, сгенерируйте случайную позицию в диапазоне [0, 16 * 8) и установите соответствующий бит равным 1. Если бит ранее был равен нулю, значит, вы только что добавили бит в массив. Повторяйте это, пока не добавите n биты.