c# – 需要一种随机选择两个位掩码中的公共位的方法

概述想象一下两个位掩码,为简单起见,我只使用8位： 0110101010111011 第2,第4和第6位都是1.我想随机选择其中一个常见的“on”位.但我想在O(1)中这样做. 到目前为止我发现这样做的唯一方法是在一个中选择一个随机的“on”位,然后检查另一个以查看它是否也打开,然后重复直到我找到匹配.这仍然是O(n),在我的情况下,两个掩码中的大多数位都是关闭的.我当然&他们一起初步检查是否有任何 想象一下两个位掩码,为简单起见,我只使用8位：

0110101010111011

第2,第4和第6位都是1.我想随机选择其中一个常见的“on”位.但我想在O(1)中这样做.

到目前为止我发现这样做的唯一方法是在一个中选择一个随机的“on”位,然后检查另一个以查看它是否也打开,然后重复直到我找到匹配.这仍然是O(n),在我的情况下,两个掩码中的大多数位都是关闭的.我当然&他们一起初步检查是否有任何共同的位.

有没有办法做到这一点？如果是这样,我可以将我的功能速度提高约6％.如果重要的话,我正在使用C#.谢谢！

麦克风

@H_502_13@解决方法 如果你愿意以可能不均匀的概率为代价来获得O(lg n)解,则递归地进行半分裂,即使用上半部分设置和下半部分设置.如果两者都非零,则随机选择一个,否则选择非零值.然后将剩下的一半分成等等.这将对32位数进行10次比较,可能没有你想要的那么少,但优于32.

您可以通过随机选择高半部分或低半部分来节省一些,并且如果没有击中另一半,并且如果有击中一半测试.

随机数只需要生成一次,因为在每次测试时只使用一位,只需在完成后将用完的位移出.

如果你有很多位,这将更有效.我不知道你怎么能把它归结为O(1).

例如,如果你有一个32位数字,并且带有0xffff0000或0x0000ffff的anded组合,如果结果是非零的(比如你用0xffff0000表示),则使用0xffff00的0​​x00ff0000,依此类推,直到你得到一位.这最终成了很多繁琐的代码. 32位需要5层代码.

总结

以上是内存溢出为你收集整理的c# – 需要一种随机选择两个位掩码中的公共位的方法全部内容，希望文章能够帮你解决c# – 需要一种随机选择两个位掩码中的公共位的方法所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。