如果可能，从 O(1) 中的 32 位值中选择随机位

首先，我建议以您在问题中建议的简单，直接，明显的方式来执行此操作：创建一个值数组，随机选择一个元素。是的，这会分配内存等等。首先优化代码的可读性和正确性;只有当您有明显的性能问题时，才应该对其进行优化。

如果您确实想将其优化为有点叽叽喳喳，此页面是我的首选资源：http://graphics.stanford.edu/~seander/bithacks.html

您需要在此处使用的算法是：

• 首先，选择你最喜欢的算法来确定汉明权重——即"有多少位？ 称该号码为 n。
• 现在从 1 到 n 中选择一个随机数 r
• 现在阅读名为"选择具有给定计数的位位置"的算法。 这将取您的数字 r，并为您提供从高端开始的第 r 个真实位的位位置。 页面上给出的代码用于多头;为整数修改它应该很简单。

我注意到许多这些算法的一个关键特征是它们是无分支的。当你试图从算法中榨取最后一盎司的性能时，请记住，每个"如果"都会扼杀性能。"if"表示缓存中有代码未运行，因为您从它分支出来，因此您更有可能丢失缓存。 "如果"表示分支预测器有机会做出错误的选择。在CLR级别，每个"if"都意味着更多的基本块，这意味着抖动进行流动分析的工作更多。等等。

您只需事先创建掩码，然后选择与源值匹配的掩码：

uint source = 631;
uint[] masks = Enumerable.Range(0, 32).Select(i => (uint)1 << i).ToArray();
uint[] matchingMask = masks.Where(m => (m & source) == m).ToArray();

现在matchingMask包含构成source值的值，在本例中为： 1, 2, 4, 16, 32, 64, 512 .

然后从matchingMask中选择一个随机元素。

如果你想要位位置，你可以使用索引Select()重载，如下所示：

var matchingMask = masks.Select((m, i) => new { Index = i, Mask = m}) 
                        .Where(m => (m.Mask & source) == m.Mask)
                        .ToArray();

这实际上是可能的。这里有一个 64 位解决方案。

我已将其转换为以下 C# 代码。它是 O(1(，因为操作数不依赖于设置的位数：

public static uint SelectRandomSetBit(ulong v, Random rng)
{
    ulong a = v - ((v >> 1) & ~0UL / 3);
    ulong b = (a & ~0UL / 5) + ((a >> 2) & ~0UL / 5);
    ulong c = (b + (b >> 4)) & ~0UL / 0x11;
    ulong d = (c + (c >> 8)) & ~0UL / 0x101;
    ulong t = ((d >> 32) + (d >> 48));
    int   n = (int)((d * (~(ulong)0 / 255)) >> (64 - 1) * 8);
    ulong r = (uint) rng.Next(1, n+1);
    ulong s = 64;
    s -= ((t - r) & 256) >> 3;
    r -= (t & ((t - r) >> 8));
    t = (d >> (int)(s - 16)) & 0xff;
    s -= ((t - r) & 256) >> 4;
    r -= (t & ((t - r) >> 8));
    t = (c >> (int)(s - 8)) & 0xf;
    s -= ((t - r) & 256) >> 5;
    r -= (t & ((t - r) >> 8));
    t = (b >> (int)(s - 4)) & 0x7;
    s -= ((t - r) & 256) >> 6;
    r -= (t & ((t - r) >> 8));
    t = (a >> (int)(s - 2)) & 0x3;
    s -= ((t - r) & 256) >> 7;
    r -= (t & ((t - r) >> 8));
    t = (v >> (int)(s - 1)) & 0x1;
    s -= ((t - r) & 256) >> 8;
    return (uint)(s-1);
}

以下是我测试它的方式：

Random rng = new Random();
ulong number = 0x0101010101010101;
int[] bits = new int[64];
for (int i = 0; i < 1000000; ++i)
    ++bits[SelectRandomSetBit(number, rng)];
for (int i = 0; i < 64; ++i)
    Console.WriteLine($"bit {i} was returned {bits[i]} times.");

您希望看到每 8 位返回大致相同的次数，而其他位都没有返回。事实确实如此。

我将其转换为 32 位是一个有趣的练习。 ;)

(无论如何，这可能是不必要的优化：一个简单的循环来计算位，然后随机选择一个可能足够快......

这应该是真的和简单的 O(1(：

byte b = 123;
Random r = new Random();
int bitNumber = r.Next(32);
var bit = (b & (1 << bitNumber-1)) != 0;

检查这个

似乎是家庭作业问题...但是，解决方案是可能的，因为您只需要查找 32 位，每个位置只有 32 个已知的提前时间值。 如果我没记错的话，它们实际上是相同的(设置了第二个位的掩码在解释为整数时具有值"2"(。

您要做的是使用准备好的位掩码构建 32 条目数组，该掩码将仅返回该位。

数组查找为 O(1(，因为无论您检索哪个位，速度都是恒定的。在这一点上，你和与原始掩码进行比较，就像你在使用位移时所做的那样，最终结果仍然是O(1(。

请注意，虽然这是 O(1(，但它可能不会比位移更快。数组是 32*4 字节的内存，因此为 128 字节。这并不大，但也不小。您需要运行一个简单的测试来确认执行多达 32 位移位指令比从数组中检索项目花费更多时间(我的猜测是数组更快，但我可能是错的(。

查找表呢？

public static class RandomExtensions
{
    public static uint GetRandomBitOf( this Random rand, uint mask )
    {
        if( mask == 0 ) return 0;
        var lo = smLookup[mask & 0xFFFF];
        var hi = smLookup[mask >> 16];
        int i = rand.Next( lo.Length + hi.Length );
        return i < lo.Length ? (uint) lo[i] : (uint) hi[i - lo.Length] << 16;
    }
    static RandomExtensions()
    {
        smLookup = new ushort[65536][];
        for( int i = 0; i < smLookup.Length; ++i )
        {
            ushort j = (ushort) i;
            smLookup[i] = Enumerable
                .Range( 0, 16 )
                .Select( b => (ushort) ( 1 << b ) )
                .Where( b => ( j & b ) != 0 )
                .ToArray();
        }
    }
    private static ushort[][] smLookup;
}

我不确定这在其他答案中的表现排名如何。 我只是添加这个答案，主要是为了在可能的实现方面保持完整性。