生成与指定上限随机INT（0 - N），而不使用/或％ [英] Generate random int with specified upper-bound (0 - n) without using / or %

问题描述

室友去面试，得到了这一个：

roommate went to an interview and got this one:

规则：

允许使用兰特（）;

RAND_MAX = 32 767;

RAND_MAX = 32 767;

没有使用部门或模数;

no use of division or modulo;

TODO：
编写一个函数，接受一个int型参数，返回
int类型范围0 - 参数

TODO: Write a function that takes one int parameter and returns int in range 0 - parameter.

头好痛，无法入睡。任何帮助AP preciated。
谢谢

Head hurts, can't sleep. Any help appreciated. Thanks

推荐答案

在我的公共领域 randlib ，我这样做与
没有浮点，没有分工，没有乘法，只是bitmasking和拒绝抽样，像这样的：

In my public domain randlib, I do it with no floating point, no division, no multiplication, just bitmasking and rejection sampling, like this:

int ojr_rand(ojr_generator *g, int limit) {
    int v, m = limit - 1;

    m |= m >> 1;
    m |= m >> 2;
    m |= m >> 4;
    m |= m >> 8; // m is smallest ((power of 2) - 1) > limit

    do {
            v = m & NEXT16(g);  // 16-bit random number
    } while (v >= limit);
    return v;
}

（限制是两个加一功率），这可以拒绝接近所产生的数的50％，但它仍然快于分割或浮动数学与最快速的RNG，并且在一般情况下，它是多

在最坏的情况下更快。此外，不同于浮点运算或MOD，它的确切的，如果你要求的3限制的意思，你得到的值0，1和2完全相等的概率，不只是大致相等。

In the worst case (limit is power of two plus one), this can reject close to 50% of the generated numbers, but it's still faster than division or floating math with most fast RNGs, and in the general case it's much faster. Also, unlike the floating point math or mod, it is exact, meaning if you ask for a limit of 3, you get values 0, 1, and 2 with exactly equal probability, not just approximately equal.

这篇关于生成与指定上限随机INT（0 - N），而不使用/或％的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！