最佳的c++方式来随机选择设置位在位集中的位置

Question

我有std::bitset<32> word，我想随机选择某个位的索引(0-31)，它是1。没有循环和计数器，我怎么能做到这一点。有适合的std::algorithm吗？如果比较容易的话，我可以将bitset转换为字符串或int，并在字符串或int上进行转换。

Answer 1

这里有第一个尝试：

std::bitset<32> bitset{...};
std::mt19937 prng(std::time(nullptr));
std::uniform_int_distribution<std::size_t> dist{1, bitset.count()};
std::size_t p = 0;
for(std::size_t c = dist(prng); c; ++p)
c -= bitset[p];
// (p - 1) is now the index of the chosen bit.

它的工作方式是对设置位进行计数，在该间隔内随机选取c，然后查找第c个设置位。

Answer 2

如果您有32位(甚至64位)的位集，更有效的解决方案是转换为整数，然后对该整数使用逐位运算来获得随机集位。

以下是如何将您的位集转换为无符号长：

std::bitset<32> word(0x1028);
unsigned long ulWord = word.to_ulong();    // ulWord == 0x1028

然后您可以使用bit Twiddling Hacks页面中的"选择比特位置"功能来有效地选择随机设置的比特：

unsigned int bitcnt = word.count();
unsigned int randomSetBitIndex = 63-selectBit(ulWord, random() % bitcnt + 1);
unsigned long randomSetBit = 1 << randomSetBitIndex;

这是完整的代码：

// Select random set bit from a bitset
#include <iostream>
#include <bitset>
#include <random>
using namespace std;
unsigned int selectBit(unsigned long long v, unsigned int r) {
// Source: https://graphics.stanford.edu/~seander/bithacks.html
// v - Input:  value to find position with rank r.
// r - Input: bit's desired rank [1-64].
unsigned int s;      // Output: Resulting position of bit with rank r [1-64]
uint64_t a, b, c, d; // Intermediate temporaries for bit count.
unsigned int t;      // Bit count temporary.
// Do a normal parallel bit count for a 64-bit integer,
// but store all intermediate steps.
a =  v - ((v >> 1) & ~0UL/3);
b = (a & ~0UL/5) + ((a >> 2) & ~0UL/5);
c = (b + (b >> 4)) & ~0UL/0x11;
d = (c + (c >> 8)) & ~0UL/0x101;
t = (d >> 32) + (d >> 48);
// Now do branchless select!
s  = 64;
s -= ((t - r) & 256) >> 3; r -= (t & ((t - r) >> 8));
t  = (d >> (s - 16)) & 0xff;
s -= ((t - r) & 256) >> 4; r -= (t & ((t - r) >> 8));
t  = (c >> (s - 8)) & 0xf;
s -= ((t - r) & 256) >> 5; r -= (t & ((t - r) >> 8));
t  = (b >> (s - 4)) & 0x7;
s -= ((t - r) & 256) >> 6; r -= (t & ((t - r) >> 8));
t  = (a >> (s - 2)) & 0x3;
s -= ((t - r) & 256) >> 7; r -= (t & ((t - r) >> 8));
t  = (v >> (s - 1)) & 0x1;
s -= ((t - r) & 256) >> 8;
return 64-s;
}
int main() {
// Input
std::bitset<32> word(0x1028);
// Initialize random number generator
std::random_device randDevice;
std::mt19937 random(randDevice());
// Select random bit
unsigned long ulWord = word.to_ulong();
unsigned int bitcnt = word.count();
unsigned int randomSetBitIndex = 63-selectBit(ulWord, random() % bitcnt + 1);
unsigned long randomSetBit = 1 << randomSetBitIndex;
// Output
cout << "0x" <<  std::hex << randomSetBit << endl;  // either 0x8, 0x20 or 0x1000
return 0;
}

在Ideone上运行。