fork(4) download
copy 
  1. // Select random set bit from a bitset
  2.  
  3. #include <iostream>
  4. #include <bitset>
  5. #include <random>
  6.  
  7. using namespace std;
  8.  
  9. unsigned int selectBit(unsigned long long v, unsigned int r) {
  10. 	// Source: http://g...content-available-to-author-only...d.edu/~seander/bithacks.html
  11. 	// v - Input:  value to find position with rank r.
  12. 	// r - Input: bit's desired rank [1-64].
  13.     unsigned int s;      // Output: Resulting position of bit with rank r [1-64]
  14.     uint64_t a, b, c, d; // Intermediate temporaries for bit count.
  15.     unsigned int t;      // Bit count temporary.
  16.  
  17.     // Do a normal parallel bit count for a 64-bit integer,
  18.     // but store all intermediate steps.
  19.     a =  v - ((v >> 1) & ~0UL/3);
  20.     b = (a & ~0UL/5) + ((a >> 2) & ~0UL/5);
  21.     c = (b + (b >> 4)) & ~0UL/0x11;
  22.     d = (c + (c >> 8)) & ~0UL/0x101;
  23.     t = (d >> 32) + (d >> 48);
  24.     // Now do branchless select!
  25.     s  = 64;
  26.     s -= ((t - r) & 256) >> 3; r -= (t & ((t - r) >> 8));
  27.     t  = (d >> (s - 16)) & 0xff;
  28.     s -= ((t - r) & 256) >> 4; r -= (t & ((t - r) >> 8));
  29.     t  = (c >> (s - 8)) & 0xf;
  30.     s -= ((t - r) & 256) >> 5; r -= (t & ((t - r) >> 8));
  31.     t  = (b >> (s - 4)) & 0x7;
  32.     s -= ((t - r) & 256) >> 6; r -= (t & ((t - r) >> 8));
  33.     t  = (a >> (s - 2)) & 0x3;
  34.     s -= ((t - r) & 256) >> 7; r -= (t & ((t - r) >> 8));
  35.     t  = (v >> (s - 1)) & 0x1;
  36.     s -= ((t - r) & 256) >> 8;
  37.     return 64-s;
  38. }
  39.  
  40. int main() {
  41. 	// Initialize random number generator
  42. 	std::random_device randDevice;
  43. 	std::mt19937 random(randDevice());
  44.  
  45. 	std::bitset<32> word(0x1028);
  46. 	unsigned long ulWord = word.to_ulong();
  47. 	unsigned int bitcnt = word.count();
  48. 	unsigned int randomSetBitIndex = 63-selectBit(ulWord, random() % bitcnt + 1);
  49.     unsigned long randomSetBit = 1 << randomSetBitIndex;
  50. 	cout << "0x" <<  std::hex << randomSetBit << endl;			// either 0x8, 0x20 or 0x1000
  51. 	return 0;
  52. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0x8
https://ideone.com/JwfZDU
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!