生成隨機數 N（小於 64）位的有效方法，其中 M 位正好等於 1

是否有一種有效的方法來實現具有以下簽名的函式：

unsigned long long int random_word(size_t n, size_t m)

這將生成一個隨機機器字（此處為 64 位），以便在設置為 時恰好m超過n最低有效位1。例如：random_word(10, 3)將生成一個 64 位隨機數，以便將 10 個 LSB 上的 3 位設置為1. 對於給定的n和m每個可能的輸出應該具有相等的機率（可能排列的均勻分佈）。

如果已知組裝位旋轉黑客來做到這一點，那很好，如果不是，我正在尋找參考和研究方向。

我猜您可以簡單地將其分為兩個問題：

1. 創建 64 - n 個隨機位，稱之為 R
2. 隨機播放 n 位，其中 m 位（在任何位置）設置為 1，稱為 P

最後你可以簡單地執行 R | P（假設大端符號）。

洗牌元素列表是幾乎所有語言中都存在的操作。如果有任何效率低下，那就是洗牌算法（儘管 Fisher-Yates 是最優的，所以你會期望某種形式的算法，可能效率低下是在一個範圍內獲取值……）。

選擇問題 $ k $ 位從 $ 64 $ 最終歸結為計算一個均勻隨機的整數 $ r $ 和 $ 0 \leq r < \frac{64!}{k!(64-k)!} $ 然後對其進行解碼以確定哪些位。這 $ k! $ 分母很煩人，但我們可以忽略它，因為我們可以讓我們的算法有 $ k! $ 映射到相同輸出的隨機數（設置位 0 然後設置位 4 與設置位 4 然後設置位 0 相同）。現在我們只需乘以從 $ 64 $ ： 和 $ k=4 $ 這等於 $ 64 * 63 * 62 * 61 $ .

所以為了效率，你選擇一個隨機數 $ 0 \le r_0 < 64 $ ，然後另一個 $ 0 \le r_1 < 63 $ … 通過 $ 0 \le r_{k-1} < 64-(k-1) $ 每次使用 $ r_n $ 在剩餘的未設置位中進行選擇。

我將以下 Python 程式碼放在一起展示了這個想法，儘管它並不快或任何東西：

# b = size of integer type
# n = number of set bits
# random_limited(x) is some function returning [0, x) sufficiently uniformly
def random_n_set_bits(b, n):
   assert b > 0
   assert n >= 0 and n <= b
   result = 0
   available = list(range(b))
   for i in range(n):
       index = random_limited(len(available))
       bit = available[index]
       available = available[:index] + available[index + 1:]
       result |= (1 << bit)
   return result

引用自：https://crypto.stackexchange.com/questions/72722