需要一种在两个位掩码中随机选取一个公共位的方法吗

如果你愿意有一个O(lg n)解,以可能的不均匀概率为代价,递归地进行半分裂,即用位集的上半部分和下半部分。如果两者都不是零,则随机选择一个,否则选择非零的一个。然后将剩下的部分分成两半,以此类推。对于一个32位的数字,这将需要10次比较,可能没有你想要的那么少,但比32位更好。

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

例如,如果您首先有一个32位的数字,并且如果结果非零(假设您与0xffff0000进行and运算),则使用0xff000000或0x00ff0000进行and运算,依此类推,直到达到一位。这最终是一个冗长的代码。32位需要5层代码。

你想要均匀的随机分布吗?如果是这样的话,我看不出有什么好的方法来计算比特数,然后随机选择一个,或者随机选择一个比特,直到你找到一个设置好的。

unsigned int pick_random(unsigned int w, int size) {
    int bitpos = rng() % size;
    unsigned int mask = ~((1U << bitpos) - 1);
    if (mask & w)
        w &= mask;
    return w - (w & (w-1));
}

哪里 rng() 是你的随机数发生器, w size 以位表示的单词的相关大小(可以是机器字号,也可以是较小的,只要不设置单词的高位)。那么,作为你的例子,你用 pick_random(0x6a & 0xbb, 8) 或者任何你喜欢的价值观。

此函数均匀地随机选择两个掩码中的高位。如果有的话 没有可能的位可以选择,而是返回零。运行时间是O(n),其中n是anded掩码中的高位数。因此,如果掩码中的高位数较少,那么即使最坏的情况是O(n),当所有位都为高位时,该函数也会更快。C语言实现如下:

unsigned int randomMasksBit(unsigned a, unsigned b){
    unsigned int i = a & b; // Calculate the bits which are high in both masks.
    unsigned int count = 0
    unsigned int randomBit = 0;
    while (i){ // Loop through all high bits.
        count++;
        // Randomly pick one bit from the bit stream uniformly, by selecting 
        // a random floating point number between 0 and 1 and checking if it 
        // is less then the probability needed for random selection.
        if ((rand() / (double)RAND_MAX) < (1 / (double)count)) randomBit = i & -i;
        i &= i - 1; // Move on to the next high bit.
    }
    return randomBit;
}

诀窍是,虽然很容易得到最低的集合位和最高的集合位,但为了获得均匀分布,我们需要随机选择一个分区点,然后随机选择是选择它下面的最高位还是上面的最低位(如果返回0,则尝试另一种方法)。

为了让步骤更容易遵循,我比平常更详细地分析了这一点。关于常数计时,我能看到的唯一问题是Math.Pow和Math.Log是否应该考虑为O(1)。

public static uint FindRandomSharedBit(uint x, uint y)
{//and two nums together, to find shared bits.
  return FindRandomBit(x & y);
}
public static uint FindRandomBit(uint val)
{//if there's none, we can escape out quickly.
  if(val == 0)
    return 0;
  Random rnd = new Random();
  //pick a partition point. Note that Random.Next(1, 32) is in range 1 to 31
  int maskPoint = rnd.Next(1, 32);
  //pick which to try first.
  bool tryLowFirst = rnd.Next(0, 2) == 1;
  // will turn off all bits above our partition point.
  uint lowerMask = Convert.ToUInt32(Math.Pow(2, maskPoint) - 1);
  //will turn off all bits below our partition point
  uint higherMask = ~lowerMask;
  if(tryLowFirst)
  {
    uint lowRes = FindLowestBit(val & higherMask);
    return lowRes != 0 ? lowRes : FindHighestBit(val & lowerMask);
  }
  uint hiRes = FindHighestBit(val & lowerMask);
  return hiRes != 0 ? hiRes : FindLowestBit(val & higherMask);
}
public static uint FindLowestBit(uint masked)
{                                  //e.g  00100100
  uint minusOne = masked - 1;      //e.g. 00100011
  uint xord = masked ^ minusOne;   //e.g. 00000111
    uint plusOne = xord + 1;       //e.g. 00001000
    return plusOne >> 1;           //e.g. 00000100
}
public static uint FindHighestBit(uint masked)
{
    double db = masked;
    return (uint)Math.Pow(2, Math.Floor(Math.Log(masked, 2)));
}

我相信,如果你想要制服,那么答案就必须是 Theta(n) 在位数方面,如果它必须对所有可能的组合工作。

下面的C++片段(被盗)应该能够检查任何给定的num是否是2的幂。

    if (!var || (var & (var - 1))) {
        printf("%u is not power of 2\n", var);
    }
    else {
        printf("%u is power of 2\n", var);
    }

如果您没有足够的位需要担心,则可以使用查找表获得O(1):

var lookup8bits = new int[256][] = {
    new [] {},
    new [] {0},
    new [] {1},
    new [] {0, 1},
    ...
    new [] {0, 1, 2, 3, 4, 5, 6, 7}
};

否则,您可以使用(x&-x) ,假设2s补码。例如,如果x=46=101110b,则-x=111…111010010b,因此x&-x=10。 您可以使用此技术在O(n)时间内枚举x的设置位,其中n是x中的设置位数。

请注意,计算一个伪随机数需要花费大量时间 比枚举x中的设置位还要长!

这不能在O(1)中完成,对于固定数量的N位的任何解(除非它真的非常可笑地愚蠢)都有一个恒定的上界,即N。