c++ - 在位集中随机选择设置位位置的最佳 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第 th 个设置位。

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上运行它。