random - 如何在不浪费比特的情况下从随机比特流中生成[0，n]范围内的随机整数？

Question

我有一个(均匀的)随机比特流，我想从中均匀地生成[0，n]范围内的随机整数，而不会浪费比特。 (我考虑的是浪费的位，这些位浪费了floor(log_2(n))+ 1，但前提是总是可以使用不多于此的位。)例如，如果n = 5，则算法为寻找应该使用不超过三位。如何才能做到这一点？

Answer 1

这等效于在两组不同(有限)基数之间找到双向函数。是不可能的。