Лучший способ 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-битный) набор битов, более эффективным решением было бы преобразование в целое число, а затем использование побитовых операций с этим целым числом для получения случайного набора битов.

Вот как вы можете преобразовать свой битовый набор в unsigned long:

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

Затем вы можете использовать функцию "Выбор позиции бита" на странице " Битовые битовые хаки", чтобы эффективно выбрать случайный бит:

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.