Implementation of the procedure RANDOM(a, b) that only makes calls to RANDOM(0, 1).

Implementation of the procedure RANDOM(a, b) that only makes calls to RANDOM(0, 1).  This is the question asked in book "Introduction to Algorithm."  I spent some time figuring out the following solution implemented in Java.  The assumption is that we can get random number 0 and 1 which I use Java class Random to generate.

import java.util.Random;
public class RandomGenerator {
    private static Random rand = new Random();

    /**
     * generate a random nubmer between a (inclusive) and b (exclusive)
     */
    public static int random(int a, int b) {
        if (a >= b) {
            throw new UnsupportedOperationException("2nd param must be greater than 1st param");
        }
        return a + generate(b - a);
    }
    /**
     * generate the random between 0 to a (exclusive)
     */
    private static int generate(int a) {
        int run = leastPowerOfTwo(a);

        while (true)  {
            int power = 1;
            int sum = 0;
            for (int i = 0; i < run; i++) {
                sum += random01() * power;
                power *= 2;
            }
            if (sum < a) {
                return sum;
            }
        }
    }

    /**
     * find the least power of 2 which is greater than or equal to the given input a
     */
    private static int leastPowerOfTwo(int a) {
        int power = 0;
        int temp = a;
        while (temp > 0) {
            temp >>>= 1;
            power++;
        }
        //if a is a power of 2
        if ((a & (a - 1)) == 0) {
            power--;
        }
        return power;
    }

    /**
     * a method to randomly generate 0 or 1
     * @return 0 or 1
     */
    private static int random01() {
        return rand.nextInt(2);
    }
}

The trick is to use the binary representation for the generated random number.  For example, to generate a random within [0, 5),  we need to call random(0, 1) 3 times since 2 ^ 3 = 8.  If call random(0, 1) 2 times, we only have 2 ^ 2 = 4 random numbers.  We only need to keep random number less than 5, and if we get a number is greater than 4, we just retry until we get the number is less than 5.   Below is the binary representation for 3 runs of random(0, 1)

#run #3   #2   #1
          0    0     0        0
          0    0     1        1
          0    1     0        2
          0    1     1        3
          1    0     0        4
          1    0     1        5
          1    1     0        6
          1    1     1        7


The informal proof of the above algorithm is that the chance to generate each number is same (1/8).  Since we only keep the number from 0 to 4, the chance to generate the number from 0 to 4 is still same.  Then the above algorithm does generate the correct random numbers.  I ran this program on my machine to generate random number from 7 to 12 (exclusive) for 10 million times, and here is the result:

7:   1997855
8:   2000311
9:   2000140
10: 2000369
11: 2001325