How to generate n random 1s in an unsigned char ar

Question

This is a different question from the one I just asked and it is more challenging.

I have an unsigned char array, say unsigned char A[16]. I need to generate a mask vector which i will apply to my array A[16].

It should contain n number of '1's, where 0 < n < 16*8 (The mask vector can be an array B[16] as long as there are n number of '1's in the array)

I also need these n number of '1's distributed randomly in the vector.

How can I do this in c/c++?

Thank you!

Edit: My thought is as follows: I will generate n random numbers (checking needs to be done to make sure all n numbers are not the same) and store them in array tmp[n]. Then mask is generated based on shifting.

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

You have an array of 16 unsigned chars, which can be seen as 16 * 8 bits. To generate a random mask with n 1 bits in it, generate a random position in the range [0, 16*8) and set the corresponding bit to 1. If the bit was previously zero, then you have just added a bit to the array. Repeat this until you have added n bits.

Answer 2

Generate random (i,j) pair of numbers, where i < 16 and j < 8. If the bit at position B[i]&(1<<j) is not set, set it and increment "count". Loop until "count" reaches "n".

A bit of code (untested):

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;
        }
    }
}

Exercise, for the challenge: remove magic constant 16 from the code.

Edit: The modification suggested in your comments contains a nasty bug. Here is a test program to play with the way bits are distributed in your output mask.

#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;
        }
    }
}

When this program is run, it will try every value of n from 0 to 16*8 and generate a random mask with n bits, then verify that exactly n bits are set. If any error occurs (for some value of n, some k!=n bits are set), a message is output.

If I change the condition to if ( (B[i]^mask) != 0 ), I get consistent errors in the output. Every run produces at least 1 error message. The original condition if ( (B[i]&mask) == 0 ) consistently produces 0 error messages.