algorithm - 有效地生成具有固定设置位和已知按位与结果的随机二进制数

Question

给定 A 中的输入二进制数列表和 B 中的输出二进制数列表，为所有满足按位与的 X 寻找一个值。即 A 和 X = B，其中 A 有 6 个设置位，B 有 0 到 6 个设置位，X 有 12 个设置位。 A、B 和 X 中的所有数字都是 128 位长。

类似于这个问题:Most efficient method of generating a random number with a fixed number of bits set 但我还需要该随机数以在使用一组已知的二进制数进行按位运算时产生已知的二进制结果。

一个幼稚的想法:生成一个随机的 128 位数字 X，其中设置了 12 位，然后针对 A 中的所有数字测试它，看它是否生成 B。如果没有，则将X 中的位，然后重试。

我知道一定有更好的算法。

澄清:B 与 A 相同，只是 A 中设置的部分或全部位 (1s) 现在已在 B 中随机设置为 0。

更新我的幼稚想法:

I just figured out that whenever a bit in A is 1, corresponding bit in X will be equal to corresponding bit in B since 1 AND xBit = bBit. When the bit in A is 0, then the xBit is unknown (0 or 1). So for each number in A, I can obtain string X made up of 1s, zeros and unknown y. e.g. yy00011y10010y10... then I could compare all these strings X to one another and find a "fit" for a unique X by replacing the y with 1s and 0s. I'm not sure if this is the best way, but it is probably better than guessing and checking. Any thoughts on this, or how to find such a fit? Thanks

Answer 1

您可以在 Binary Decision Diagram 中对约束进行编码，应用计算机编程艺术第 4A 卷中的算法 C(计算每个 BDD 节点的解决方案数量)，然后从中生成随机解决方案。

对于每个节点，您可以选择“高”或“低”，具体取决于您将该变量选择为 1 还是 0。这两种方式都有一定数量的解决方案，我们称它们为#H 和#L。为了随机选择每个解决方案的可能性均等，请选择概率为 #H/(#H + #L) 的高(即，将此变量设置为 1)，并以 1 减去该概率选择低。继续这样做，直到您进入汇节点。这通常会起作用，而不仅仅是这个问题。

BDD 可以通过交叉(算法在 TAOCP 中给出，但当然存在于每个 BDD 库中)一个 BDD 来构造，该 BDD 编码 A & X = B 约束(微不足道 - 只是一个线性 BDD，强制某些位保持不变并忽略所有不受约束的位)和一个 BDD，强制 X 的 popcnt 为 12(这看起来像一个 12 x 128 的节点“网格”，附加了一些额外的链，每个额外的设置位都指向底部水槽)。我想整个 BDD 也可以立即构建，而不是分两步构建，但这听起来有点烦人。

---

也可以更直接的生成一个非随机的解，先放入最多6个强制位:

X = B // assuming A & B = B

然后把剩下的 1 放在“无害”的地方，

R = (1 << (12 - popcnt(X))) - 1 // right number of 1's, wrong place
X |= _pdep_u64(R, ~A);

A 不约束的任何地方都很好，它们从下到上填满，但如果我们不关心随机性，那也很好。另请注意，我使用的是 _pdep_u64，而不是 _pdep_u128，但这没关系，因为低 64 位总是有最多 12 位的空间，A 仅设置了 6 位至少有 58 个地方可以放剩余的比特。