lundi 15 février 2016

How to randomize lowest bits in a 64 bit pattern

I am interested in learning more about the concepts behind bit shifting and the manipulation of randomly generated bits. Below is some code that prints 20 random 64 bit patterns. "rand_bits" uses the C standard rand() to return a 64 bit pattern with all zeros except for the lowest bits, which are randomized. The number of low randomized bits is provided by the only parameter to the function.

   const int LINE_CNT = 20;

    void print_bin(uint64_t num, unsigned int bit_cnt);

    uint64_t rand_bits(unsigned int bit_cnt);

    int main(int argc, char *argv[]) {

        int i;

        srand(time(NULL));
        for(i = 0; i < LINE_CNT; i++) {
            uint64_t val64 = rand_bits(64);
            print_bin(val64, 64);
        }
    return EXIT_SUCCESS;
    }


    void print_bin(uint64_t num, unsigned int bit_cnt) {

        int top_bit_cnt;

        if(bit_cnt <= 0) return;
        if(bit_cnt > 64) bit_cnt = 64;

        top_bit_cnt = 64;
        while(top_bit_cnt > bit_cnt) {
            top_bit_cnt--;
            printf(" ");
        }

        while(bit_cnt > 0) {
            bit_cnt--;
            printf("%d", (num & ((uint64_t)1 << bit_cnt)) != 0);
        }
        printf("\n");

        return;
    }


    /*
     * Name: rand_bits
     * Function: Returns a 64 bit pattern with all zeros except for the
     *           lowest requested bits, which are randomized.  
     * Parameter, "bit_cnt":  How many of the lowest bits, including the
     *           lowest order bit (bit 0) to be randomized
     * Return: A 64 bit pattern with the low bit_cnt bits randomized.
     */
    uint64_t rand_bits(unsigned int bit_cnt) {


        printf("int bit_cnt:", bit_cnt);
        uint64_t result = rand();
        uint64_t result_1 = result>>5;
// uint64_t result_1 = result>>7;

//return result;
        return result_1;

    }

For example, if the function is called with 24 as the argument value, it might return a 64 bit pattern, such as:

0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_​1101_0110_0101_1110_0111_1100

Currently the function rand_bits may show more than 15 random bits coming from the rand() function, but this is by NO means guaranteed.

I thought that to get the 40 bits like in the example I could right shift the bits, but that does not seem to be the concept. Does this require a bit mask of the higher order bits or a mod calculation on the random number generator?

Any suggestions of how to return a bit pattern of all zeros with its lowest bits (bit_cnt) randomized?




Aucun commentaire:

Enregistrer un commentaire