c++ - 如何在 C/C++ 中的 unsigned char 数组中生成 n 个随机 1？

Question

这是一个与我刚才问的不同的问题，它更具挑战性。

我有一个无符号字符数组，比方说 无符号字符 A[16]。 我需要生成一个掩码 vector ，我将其应用于我的数组 A[16]。

它应该包含 n 个“1”，其中 0 < n < 16*8(掩码 vector 可以是数组 B[16]，只要数组中有 n 个“1”)

我还需要 vector 中随机分布的这 n 个“1”。

我如何在 c/c++ 中执行此操作？

谢谢!

编辑: 我的想法是这样的: 我将生成 n 个随机数(需要进行检查以确保所有 n 个数字都不相同)并将它们存储在数组 tmp[n] 中。然后根据shifting生成mask。

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

Answer 1

生成随机 (i,j)一对数字，其中 i < 16和 j < 8 .如果位在B[i]&(1<<j)未设置，设置它并增加“计数”。循环直到“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]&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]&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) & 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 的每一个值来自 0至 16*8并使用 n 生成一个随机掩码位，然后准确地验证 n位被设置。如果发生任何错误(对于 n 的某些值，某些 k!=n 位已设置)，将输出一条消息。

如果我将条件更改为 if ( (B[i]^mask) != 0 ) ，我在输出中得到一致的错误。每次运行都会产生至少 1 条错误消息。原状if ( (B[i]&mask) == 0 )始终产生 0 个错误消息。