// 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: http://g...content-available-to-author-only...d.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() {
	// Initialize random number generator
	std::random_device randDevice;
	std::mt19937 random(randDevice());
	
	std::bitset<32> word(0x1028);
	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;
	cout << "0x" <<  std::hex << randomSetBit << endl;			// either 0x8, 0x20 or 0x1000
	return 0;
}