c++ - 不同位的随机对

Question

我有以下问题。我有一个以二进制表示的数字。我需要一种方法来随机选择其中两个不同的位(即找到 1 和 0)。除此之外，我还对该数字进行了其他操作(反转序列、置换序列……)这些是我已经使用过的方法:

• 记录所有的 1 和 0。当我创建二进制数的二进制表示时，我存储了 0 和 1 的位置。这样我就可以为一个列表选择一个索引，并从另一个列表中选择一个索引。然后我有两个不同的位。为了运行我的其他操作，我从基本交换操作创建了这些操作，这些操作在操作时更新 1 和 0 的索引。因此我有第三个列表存储每个位的列表索引。如果一个位是 1，我知道在列表中的哪里可以找到所有的索引(对于零也是如此)。
• 当完成不需要位不同的操作时，上述方法会产生一些开销。因此，另一种方法是在需要不同位时创建列表。

有没有人有更好的主意来做到这一点？我需要这些操作非常快(我正在使用 popcount、clz 和其他二进制操作)

Answer 1

我觉得我没有足够的信息来正确评估权衡，但也许您会发现这个想法很有用。要在一个词中找到一个随机的 1(通过 popcount 和 reservoir 采样在多个词中找到一个 1；通过补码找到一个 0)，首先测试 popcount。如果 popcount 很高，则随机统一生成索引并测试它们，直到找到一个。如果 popcount 为中等，则采用具有统一随机掩码的按位 AND(但如果 AND 为零，则保留原始值)以减少 popcount。当 popcount 较低时，使用 clz 高效地编译(小)候选列表，然后随机均匀采样。