c# - 需要一种方法来随机选择两个位掩码中的公共(public)位

Question

假设有两个位掩码，为简单起见，我只使用 8 位:

01101010
10111011

第 2、4 和 6 位都是 1。我想随机选择那些常见的“on”位之一。但我想在 O(1) 中执行此操作。

到目前为止，我找到的唯一方法是在一个中随机选择一个“打开”位，然后检查另一个以查看它是否也打开，然后重复直到找到匹配项。这仍然是 O(n)，在我的例子中，两个掩码中的大部分位都关闭了。我当然会将它们放在一起，以初步检查是否有任何共同点。

有没有办法做到这一点？如果是这样，我可以将函数的速度提高大约 6%。如果重要的话，我正在使用 C#。谢谢!

迈克

Answer 1

如果您愿意有一个 O(lg n) 的解决方案，以可能不均匀的概率为代价，递归地对半拆分，即设置上半部分的位和设置下半部分的位。如果两者都非零，则随机选择一个，否则选择非零。然后将剩下的部分分成两半，等等。对于一个 32 位数字，这将需要进行 10 次比较，可能没有您想要的那么少，但比 32 位要好。

您可以通过随机选择高半部分或低半部分来节省一些和，如果没有命中则使用另一半，如果有命中则进行测试。

随机数只需要生成一次，因为每次测试只使用一位，用完后只需将使用过的位移出即可。

如果你有很多位，这会更有效率。不过，我看不出如何将其降低到 O(1)。

例如，如果您首先有一个 32 位数字，并且如果结果为非零，则与 0xffff0000 或 0x0000ffff 的 anded 组合(假设您使用 0xffff0000 anded)继续使用 0x00ff0000 的 0xff000000，依此类推，直到您得到一个少量。这最终会成为很多乏味的代码。 32 位需要 5 层代码。