Databases
StackOverflow2013
Postsdbo
PO
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    text
    copied!<p>Here is a version based on an <a href="http://graphics.stanford.edu/~seander/bithacks.html##SelectPosFromMSBRank" rel="nofollow noreferrer">algorithm</a> from <a href="http://graphics.stanford.edu/~seander/bithacks.html" rel="nofollow noreferrer">Bit Twiddling Hacks</a> to select the nth set bit of an integer. For this case, we simply select n at random.</p> <p>The code has been ported to C#, made to work directly on 32-bit signed integers, and count from the right instead of the left. Furthermore, the optimization to remove all branches has not been preserved here as it yielded slower code on my machine (Intel Core 2 Quad Q9450).</p> <p>The description on the Bit Twiddling Hacks page does not give much insight into how the algorithm works. I have taken the time to step through and reverse engineer it and what I found is described in detail in the comments below.</p> <p>In my tests, this algorithm performs very similarly to Kyteland's excellent flipRandomBit over input that is distributed randomly across the full range of 32-bit integers. However, flipRandomBit is slightly faster for numbers with significantly fewer set bits than cleared bits. Conversely, this algorithm is slightly faster for numbers with significantly more set bits than cleared bits.</p> <p>The OP's benchmark consists entirely of small positive integers, which do not stress flipRandomBit's worst case. If this is an indication of the expected input, then all the more reason to prefer flipRandomBit.</p> <pre><code>static int ClearRandomSetBit(int input) { /////////////////////////////////////////////////////////////////////// // ** Step 1 ** // Count the set bits //////////////////////////////////////////////////////////////////////// // magic numbers const int m2 = 0x55555555; // 1 zero, 1 one, ... const int m4 = 0x33333333; // 2 zeros, 2 ones, ... const int m8 = 0x0f0f0f0f; // 4 zeros, 4 ones, ... // sequence of 2-bit values representing the counts of each 2 bits. int c2 = input - ((input &gt;&gt; 1) &amp; m2); // sequence of 4-bit values representing the counts of each 4 bits. int c4 = (c2 &amp; m4) + ((c2 &gt;&gt; 2) &amp; m4); // sequence of 8-bit values representing the counts of each 8 bits. int c8 = (c4 + (c4 &gt;&gt; 4)) &amp; m8; // count set bits in input. int bitCount = (c8 * 0x1010101) &gt;&gt; 24; /////////////////////////////////////////////////////////////////////////////////// // ** Step 2 ** // Select a random set bit to clear and find it using binary search with our // knowledge of the bit counts in the various regions. /////////////////////////////////////////////////////////////////////////////////// // count 16 right-most bits where we'll begin our search int count = (c8 + (c8 &gt;&gt; 8)) &amp; 0xff; // position of target bit among the set bits int target = random.Next(bitCount); // distance in set bits from the current position to the target int distance = target + 1; // current bit position int pos = 0; // if the target is not in the right-most 16 bits, move past them if (distance &gt; count) { pos += 16; distance -= count; } // if the target is not in the next 8 bits, move past them count = (c8 &gt;&gt; pos) &amp; 0xff; if (distance &gt; count) { pos += 8; distance -= count; } // if the target is not in the next 4 bits, move past them count = (c4 &gt;&gt; pos) &amp; 0xf; if (distance &gt; count) { pos += 4; distance -= count; } // if the target is not in the next 2 bits, move past them count = (c2 &gt;&gt; pos) &amp; 0x3; if (distance &gt; count) { pos += 2; distance -= count; } // if the bit is not the next bit, move past it. // // Note that distance and count must be single bits by now. // As such, distance is greater than count if and only if // distance equals 1 and count equals 0. This obversation // allows us to optimize away the final branch. Debug.Assert((distance &amp; 0x1) == distance); Debug.Assert((count &amp; 0x1) == count); count = (input &gt;&gt; pos) &amp; 0x1; pos += (distance &amp; (count ^ 1)); Debug.Assert((input &amp; (1 &lt;&lt; pos)) != 0); return input ^ (1 &lt;&lt; pos); } </code></pre>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload