有没有可能在随机生成的64位数上 Select 一系列按位操作，使得最终结果中的位具有给定的被置位概率？我的目标是写一个函数，它在[0，1)范围内取一个double，并生成一个具有该比例位的long，只通过在随机生成的long上使用按位操作OR和AND.
我的 idea 是，这将减少到最小化的错误，|p—(4^n—1)/(4^m)|其中p是期望的比率，m代表总操作，n代表OR的数量.这是因为，将k个长函数加在一起后得到的比率是1/(4^k)，而将n个长函数加在一起后得到的比率应该是1—1/4^n，所以两者相加后的比率是(4^k—1)/(4 ^(k + n)).这就是我被卡住的地方，因为我不知道如何找到k或n的最佳值.
如果我理解正确的话，这听起来很像俄国农民乘法.考虑到随机生成的long将使每个比特独立，并且每个比特以50%的概率设置.假设(为了递归)我们有你想要的函数f(p)，那么
rand() gives the same distribution as f(0.5)
f(p) & f(q) gives the same distribution as f(p*q)
f(p) | f(q) gives the same distribution as f(p + q - p*q)
假设我们要找f(0.9)个.我们知道
f(0.9) = f(0.5) | f(x) where 0.5 + x - 0.5*x = 0.9, i.e. 0.5x = 0.4
所以现在我们要找f(0.8)个.我们知道
f(0.8) = f(0.5) | f(x) where 0.5x = 0.3
f(0.6) = f(0.5) | f(x) where 0.5x = 0.1
f(0.2) = f(0.5) & f(x) where 0.5x = 0.2
f(0.4) = f(0.5) & f(x) where 0.5x = 0.4
f(0.8) = f(0.5) | f(x) where 0.5x = 0.3
[...]
这个递归永远不会真正完成；但是在我们喜欢的任何时候，我们都可以触底并开始重新缠绕堆栈.
f(0.9) = R | R | (R & R & (R | R | (R & R & ...)))
例如，这个C代码给出了一个非常接近p = 0.9的分布:
#define R (rand() % 256)
unsigned get09() {
unsigned x = R; // 0.5
x |= R; // 0.75
x |= R; // 0.875
x &= R; // 0.4375
x &= R; // 0.21875
x |= R; // 0.609375
x |= R; // 0.8046875
x |= R; // 0.90234375
return x;
}
现在，你能不能通过使用生产而不是直接使用R得到even closer—例如，我们能不能使用f(0.9) = f(0.684) | f(0.684)的事实，然后寻找产生f(0.684)的方法？当然.
现在，也许这是Baader—Meinhof效应的作用，但这实际上(偶然！)感觉就像是一个类似于https://mathoverflow.net/questions/466176/what-is-the-proper-name-for-this-tersest-path-problem-in-infinite-craft的有向超图的"三阶路径"问题——关于某些理论，请参见https://quuxplusone.github.io/blog/2024/03/03/infinite-craft-theory/和Knuth卷2 § 4.6.3"幂的判断".我们正在寻找从$V_0 ={0.5}$到p的三进制路径，使用的是一个操作$E $，实际上是two个可能的操作:&和|.因此，从{0.5}，我们可以在一个步骤中到达{0.5，0.25，0.75，0.125，0.625，0.375，0.875，0.1875，0.8125}中的任何一个；依此类推；你只想知道要走多少步才能达到p的某个数值.
编辑:我突然想到，这些目标在基数2更好地代表，而不是基数10.从{0.1}(基数为2)，我们可以在一个步骤中到达{0.1，0.01，0.11}中的任何一个；在两个步骤中到达{0.1，0.01，0.11，0.001，0.1101}中的任何一个；当然，不可能达到任何p，其二进制表示具有无限多个1位(例如p = 0.9 = 0.11p1p1. 2)；但我们可以任意接近.
看起来一般的解决方案是(就像俄国农民乘法一样)把目标写成二进制，然后把1变成|s和0变成s.&例如，要达到p = 0.7，即0.101|&||&&|||...111... 2，我们会写这个，其中从底部向上读取，逐位操作是|&||&&|||...，每个逐位操作都会增加一个前导位到结果.
#define R (rand() % 256)
unsigned get07() {
unsigned x = R | R; // 0.11
x |= R; // 0.111
x &= R; // 0.0111
x &= R; // 0.00111
x |= R; // 0.100111
x |= R; // 0.1100111
x &= R; // 0.01100111
x |= R; // 0.101100111
return x;
}