CODEWITHSUNDEEP
algorithmbit-manipulation
Sahil
Sahil

Reputation: 9478

How to generate number between a low and a high number using just a bit?

I was asked this question in a interview, so I don't want the solution, just the guidance regarding how to approach it.

You have been given two numbers low and high. And a random generator which generates 0 and 1. I have to generate a number between low and high using that function.

I can get difference between the two numbers and somehow try to generate a number using bit manipulation. But I am not able to figure out how to do that?

Upvotes: 2

Views: 243

Answers (2)

m69 ''snarky and unwelcoming''
m69 ''snarky and unwelcoming''

Reputation: 12324

Here's a basic bit-by-bit comparison algorithm that gives a random number between low and high, using a random-bit function:

  • Decrease high by 1 and increase low by 1 (in case the random bits introduced later all equal those in high or low).
  • Create booleans high_dec and low_inc to store whether at least one 1 in high has been changed into 0, and at least one 0 in low has been changed into 1, and set both of them to false (these will help avoid the result going out of range).

  • Compare high and low bit-by-bit from MSB to LSB with these cases:

    • If you find high:1 and low:1 then store a 1 if low_inc=false or store a random bit otherwise (and update high_dec as necessary).
    • If you find high:1 and low:0 then store a random bit (and update high_dec or low_inc as necessary).
    • If you find high:0 and low:1 then store a 0 if high_dec=false or store a 1 if low_inc=false or store a random bit otherwise.
    • If you find high:0 and low:0 then store a 0 if high_dec=false or store a random bit otherwise (and update low_inc as necessary).

Note that the distribution of the random numbers is only uniform if the lowest possible result is a power of 2, and the range is a power of 2. In all cases the whole range is used, but there may be an emphasis on values near the beginning or end of the range.

function between(a, b) {
    var lo = (a + 1).toString(2).split(''),         // conversion to bit array because
        hi = (b - 1).toString(2).split(''),         // there is no bit manipulation in JS
        lc = false,                                 // low changed
        hc = false,                                 // high changed
        result = [];
    while (lo.length < hi.length) lo.unshift(0);    // add leading zeros to low
    for (var i = 0; i < hi.length; i++) {           // iterate over bits, msb to lsb
        var bit = Math.round(Math.random());        // random bit generator
        if (hi[i] == 1) {
            if (lo[i] == 1) {                       // case hi:1 lo:1
                if (lc == false) bit = 1
                else if (bit == 0) hc = true;
            } else {                                // case hi:1 lo:0
                if (bit == 0) hc = true
                else lc = true;
            }
        } else {
            if (lo[i] == 1) {                       // case hi:0 lo:1
                if (hc == false) bit = 0
                else if (lc == false) bit = 1;
            } else {                                // case hi:0 lo:0
                if (hc == false) bit = 0
                else if (bit == 1) lc = true;
            }
        }
        result.push(bit);
    }
    return parseInt(result.join(''), 2);            // convert bit array to integer
}

document.write(between(999999, 1000100) + "<BR>");

Upvotes: 1

Jean Logeart
Jean Logeart

Reputation: 53839

You can do:

  1. range = high - low
  2. find n such that 2^n-1 < range <= 2^n
  3. run the random generator n times to generate an int thanks to its binary representation. Something like 010011010 (= 154 in decimal)
  4. add the obtained number to low to get your final number!

Upvotes: 2

Related Questions