Как сгенерировать случайное целое число в диапазоне [0, n] из потока случайных битов без потери битов?

У меня есть поток (однородных) случайных битов, из которого я хотел бы генерировать случайные целые числа равномерно в диапазоне [0, n], не теряя бит. (Я рассматриваю потраченные впустую биты, которые превышают этаж (log_2 (n)) + 1, исходя из предположения, что всегда можно использовать не больше этого.) Например, если n = 5, то алгоритм я ищу следует использовать не более трех бит. Как это можно сделать?

6
задан uckelman 18 May 2011 в 21:28
поделиться