dimanche 22 octobre 2017

generate a random int given a random bit function

Suppose you're given a int randBit() function which returns, uniformly distributed, 0 or 1.

Write a randNumber(int max) function.

This is my implementation, but I can't prove/disprove that it's right.

    // max number of bits
    int i = (int)Math.floor(Math.log(max) / Math.log(2)) + 1;

    int ret = randBit();
    while (i-- > 0) {
        ret = ret << 1 | randBit();
    }

    return ret;

Aucun commentaire:

Enregistrer un commentaire