想象一下两个位掩码,为简单起见,我只使用8位：
01101010 10111011
第2,第4和第6位都是1.我想随机选择其中一个常见的“on”位.但我想在O(1)中这样做.
到目前为止我发现这样做的唯一方法是在一个中选择一个随机的“on”位,然后检查另一个以查看它是否也打开,然后重复直到我找到匹配.这仍然是O(n),在我的情况下,两个掩码中的大多数位都是关闭的.我当然&他们一起初步检查是否有任何共同的位.
有没有办法做到这一点？如果是这样,我可以将我的功能速度提高约6％.如果重要的话,我正在使用C#.谢谢！
麦克风
解决方法
如果你愿意以可能不均匀的概率为代价来获得O(lg n)解,则递归地进行半分裂,即使用上半部分设置和下半部分设置.如果两者都非零,则随机选择一个,否则选择非零值.然后将剩下的一半分成等等.这将对32位数进行10次比较,可能没有你想要的那么少,但优于32.
您可以通过随机选择高半部分或低半部分来节省一些,并且如果没有击中另一半,并且如果有击中一半测试.
随机数只需要生成一次,因为在每次测试时只使用一位,只需在完成后将用完的位移出.
如果你有很多位,这将更有效.我不知道你怎么能把它归结为O(1).
例如,如果你有一个32位数字,并且带有0xffff0000或0x0000ffff的anded组合,如果结果是非零的(比如你用0xffff0000表示),则使用0xffff00的0x00ff0000,依此类推,直到你得到一位.这最终成了很多繁琐的代码. 32位需要5层代码.
