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

Question

我有一个32位随机值(比方说631).

0...0000001001110111

每个位都是一个标志.如果可能的话,我想从这些位返回一个随机标志,进行O(1)操作.如何从给定值中选择位位置0,1,2,4,5,6或9(或它的对应值1,2,4,16,32,64,512)631？优选地,对于某些位具有至少可能的偏置.

我提出的事情:

1. • 移位值右边的随机位数(在这种情况下最多10个)
   • 看看是否设置了LSB
     • 如果是:得到一个位置(最后移位的位数); DONE
     • 如果不:
       • 如果结果值== 0; 重来
       • 如果结果值!= 0,则返回再次移位随机位

上面不是O(1),如果我们碰巧只"击中"0位,可能需要多次迭代.

2. • 掩码(和)随机值
   • 重复直到剩余2的幂或当值为0时重新开始.

同样,不幸的是,上面不是O(1).

我很确定这必须是可能的,有些bithisfting/masking /魔法......

---

编辑:

正如CodeCaster建议的那样 ; 这将给我所有设置位值:

int myvalue = 631;
var matchingmasks = Enumerable.Range(0, 32)
                              .Select(i => 1 << i)
                              .Where(i => (myvalue & i) == i)
                              .ToArray();

从结果数组中我可以选择一个随机元素,我将从给定值中找到我的"随机"位(标志).但是,这仍然需要一个(隐藏的,因为Linq)for循环,"强制"每个可能的位,结果数组的内存分配等.

Answer 1

首先,我建议你在问题中提出一个简单,直接,明显的方法:创建一个值数组,随机选择一个元素.是的,这会分配内存和诸如此类的东西.首先优化可读和正确的代码; 只有当您遇到性能问题时,才应对其进行优化.

如果您确实希望将其优化到令人讨厌的位置,那么这个页面就是我的首选资源:http://graphics.stanford.edu/~seander/bithacks.html

您需要的算法是:

• 首先,选择您最喜欢的算法来确定汉明重量 - 即"有多少位？" 拨打该号码.
• 现在从1到n选择一个随机数r
• 现在读取名为"用给定计数选择位位置"的算法.这将获取您的数字r,并从高端开始为您提供第r个真位的位位置.页面上给出的代码是长的; 它应该直接修改为int.

我注意到许多算法的一个关键特性是它们是无分支的.当您尝试从算法中获取最后一盎司的性能时,请记住每个"if"都会导致性能下降."if"表示缓存中的代码未运行,因为您从中分离出来,因此您更有可能发生缓存未命中."if"表示分支预测器有机会做出错误的选择.在CLR级别,每个"if"意味着更多的基本块,这意味着更多的抖动工作可以进行流量分析.等等.