StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POHow do you randomly zero a bit in an integer?
primarykey
Id
2001597
data
AcceptedAnswerId
2010404
AnswerCount
13
ClosedDate
CommentCount
9
CommunityOwnedDate
CreationDate
2010-01-04T19:30:43.187
FavoriteCount
5
LastActivityDate
2010-01-08T05:11:25.200
LastEditDate
2010-01-06T13:22:07.920
LastEditorUserId
40868
OwnerUserId
40868
ParentId
0
PostTypeId
1
Score
17
ViewCount
2033
LastEditorDisplayName
text
Body
Updated with newer answer and better test Let's say I have the number 382 which is 101111110. How could I randomly turn a bit which is not 0 to 0? The why; Since people ask me why, I simply need to do this, removing a bit from an integer. based on the answer here is the result(working one) I ran this <pre><code>using System; using System.Collections.Generic; using System.Collections; using System.Linq; using System.Diagnostics; namespace ConsoleApplication1 { class Program { static Random random; static void Main(string[] args) { Stopwatch sw; int[] test = new int[10] { 382, 256, 1, 257, 999, 555, 412, 341, 682, 951 }; random = new Random(42); for (int j = 0; j < 10; j++) { sw = Stopwatch.StartNew(); for (int i = 0; i < 1000000; i++) Perturb(test[j]); sw.Stop(); Console.WriteLine("Perturb " + sw.Elapsed.TotalSeconds.ToString("0.#######") + " seconds for " + test[j].ToString()); Debug.WriteLine("> Perturb " + sw.Elapsed.TotalSeconds.ToString("0.#######") + " seconds for " + test[j].ToString() + " "); } random = new Random(42); for (int j = 0; j < 10; j++) { sw = Stopwatch.StartNew(); for (int i = 0; i < 1000000; i++) FastPerturb(test[j]); sw.Stop(); Console.WriteLine("FastPerturb " + sw.Elapsed.TotalSeconds.ToString("0.#######") + " seconds for " + test[j].ToString()); Debug.WriteLine("> FastPerturb " + sw.Elapsed.TotalSeconds.ToString("0.#######") + " seconds for " + test[j].ToString() + " "); } random = new Random(42); for (int j = 0; j < 10; j++) { sw = Stopwatch.StartNew(); for (int i = 0; i < 1000000; i++) SetRandomTrueBitToFalse(test[j]); sw.Stop(); Console.WriteLine("SetRandomTrueBitToFalse " + sw.Elapsed.TotalSeconds.ToString("0.#######") + " seconds for " + test[j].ToString()); Debug.WriteLine("> SetRandomTrueBitToFalse " + sw.Elapsed.TotalSeconds.ToString("0.#######") + " seconds for " + test[j].ToString() + " "); } random = new Random(42); for (int j = 0; j < 10; j++) { sw = Stopwatch.StartNew(); for (int i = 0; i < 1000000; i++) flipRandomBit(test[j]); sw.Stop(); Console.WriteLine("flipRandomBit " + sw.Elapsed.TotalSeconds.ToString("0.#######") + " seconds for " + test[j].ToString()); Debug.WriteLine("> flipRandomBit " + sw.Elapsed.TotalSeconds.ToString("0.#######") + " seconds for " + test[j].ToString() + " "); } random = new Random(42); for (int j = 0; j < 10; j++) { sw = Stopwatch.StartNew(); for (int i = 0; i < 1000000; i++) oneBitsIndexes(test[j]); sw.Stop(); Console.WriteLine("oneBitsIndexes " + sw.Elapsed.TotalSeconds.ToString("0.#######") + " seconds for " + test[j].ToString()); Debug.WriteLine("> oneBitsIndexes " + sw.Elapsed.TotalSeconds.ToString("0.#######") + " seconds for " + test[j].ToString() + " "); } random = new Random(42); for (int j = 0; j < 10; j++) { sw = Stopwatch.StartNew(); for (int i = 0; i < 1000000; i++) ClearOneBit(test[j]); sw.Stop(); Console.WriteLine("ClearOneBit " + sw.Elapsed.TotalSeconds.ToString("0.#######") + " seconds for " + test[j].ToString()); Debug.WriteLine("> ClearOneBit " + sw.Elapsed.TotalSeconds.ToString("0.#######") + " seconds for " + test[j].ToString() + " "); } random = new Random(42); for (int j = 0; j < 10; j++) { sw = Stopwatch.StartNew(); for (int i = 0; i < 1000000; i++) FlipRandomTrueBit(test[j]); sw.Stop(); Console.WriteLine("FlipRandomTrueBit " + sw.Elapsed.TotalSeconds.ToString("0.#######") + " seconds for " + test[j].ToString()); Debug.WriteLine("> FlipRandomTrueBit " + sw.Elapsed.TotalSeconds.ToString("0.#######") + " seconds for " + test[j].ToString() + " "); } random = new Random(42); for (int j = 0; j < 10; j++) { sw = Stopwatch.StartNew(); for (int i = 0; i < 1000000; i++) ClearRandomBit(test[j]); sw.Stop(); Console.WriteLine("ClearRandomBit " + sw.Elapsed.TotalSeconds.ToString("0.#######") + " seconds for " + test[j].ToString()); Debug.WriteLine("> ClearRandomBit " + sw.Elapsed.TotalSeconds.ToString("0.#######") + " seconds for " + test[j].ToString() + " "); } Console.Read(); } public static int Perturb(int data) { if (data == 0) return 0; int minBits = (data & 0xFFFF0000) == 0 ? 16 : 32; int newData = data; do { newData &= ~(1 << random.Next(minBits)); } while (newData == data); return newData; } public static int FastPerturb(int data) { if (data == 0) return 0; int bit = 0; while (0 == (data & (bit = 1 << random.Next(32)))) ; return data & ~bit; } private static Int32 SetRandomTrueBitToFalse(Int32 p) { List<int> trueBits = new List<int>(); for (int i = 0; i < 31; i++) { if ((p >> i & 1) == 1) { trueBits.Add(i); } } if (trueBits.Count > 0) { int index = random.Next(0, trueBits.Count); return p & ~(1 << trueBits[index]); } return p; } public static int getBitCount(int bits) { bits = bits - ((bits >> 1) & 0x55555555); bits = (bits & 0x33333333) + ((bits >> 2) & 0x33333333); return ((bits + (bits >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; } public static int flipRandomBit(int data) { int index = random.Next(getBitCount(data)); int mask = data; for (int i = 0; i < index; i++) mask &= mask - 1; mask ^= mask & (mask - 1); return data ^ mask; } public static int oneBitsIndexes(int data) { if (data > 0) { var oneBitsIndexes = Enumerable.Range(0, 31) .Where(i => ((data >> i) & 0x1) != 0).ToList(); // pick a random index and update the source value bit there from 1 to 0 data &= ~(1 << oneBitsIndexes[random.Next(oneBitsIndexes.Count)]); } return data; } static private int ClearOneBit(int originalValue) { if (originalValue == 0) return 0; // All bits are already set to 0, nothing to do int mask = 0; do { int n = random.Next(32); mask = 1 << n; } while ((mask & originalValue) == 0); // check that this bit is not 0 int newValue = originalValue & ~mask; // clear this bit return newValue; } public static BitArray FlipRandomTrueBit(BitArray bits) { List<int> trueBits = new List<int>(); for (int i = 0; i < bits.Count; i++) if (bits[i]) trueBits.Add(i); if (trueBits.Count > 0) { int index = random.Next(0, trueBits.Count); bits[trueBits[index]] = false; } return bits; } public static int FlipRandomTrueBit(int input) { BitArray bits = new BitArray(new int[] { input }); BitArray flipedBits = FlipRandomTrueBit(bits); byte[] bytes = new byte[4]; flipedBits.CopyTo(bytes, 0); int result = BitConverter.ToInt32(bytes, 0); return result; } static int ClearRandomBit(int value) { return unchecked((int)ClearRandomBit((ulong)(uint)value)); } static ulong ClearRandomBit(ulong value) { // Algorithm from http://graphics.stanford.edu/~seander/bithacks.html // // "Select the bit position (from the most-significant bit) with the // given count (rank)." // // The following 64-bit code selects the position of the rth 1 bit when // counting from the left. In other words if we start at the most // significant bit and proceed to the right, counting the number of bits // set to 1 until we reach the desired rank, r, then the position where // we stop will be the final value given to s. // Do a normal parallel bit count for a 64-bit integer, // but store all intermediate steps. ulong v = value; ulong a = v - ((v >> 1) & ~0UL / 3); ulong b = (a & ~0UL / 5) + ((a >> 2) & ~0UL / 5); ulong c = (b + (b >> 4)) & ~0UL / 0x11; ulong d = (c + (c >> 8)) & ~0UL / 0x101; ulong t = (uint)((d >> 32) + (d >> 48)); // Choose a random r in the range [1-bitCount] int bitCount = (int)((d * (~0UL / 255)) >> 56); int randomRank = 1 + random.Next(bitCount); ulong r = (ulong)randomRank; // Compute s ulong s = 64; s -= ((t - r) & 256UL) >> 3; r -= (t & ((t - r) >> 8)); t = (d >> (int)(s - 16)) & 0xff; s -= ((t - r) & 256UL) >> 4; r -= (t & ((t - r) >> 8)); t = (c >> (int)(s - 8)) & 0xf; s -= ((t - r) & 256UL) >> 5; r -= (t & ((t - r) >> 8)); t = (b >> (int)(s - 4)) & 0xf; s -= ((t - r) & 256UL) >> 6; r -= (t & ((t - r) >> 8)); t = (a >> (int)(s - 2)) & 0x3; s -= ((t - r) & 256UL) >> 7; r -= (t & ((t - r) >> 8)); t = (v >> (int)(s - 1)) & 0x1; s -= ((t - r) & 256UL) >> 8; s = 65 - s; // Clear the selected bit return value & ~(1UL << (int)(64 - s)); } } } </code></pre> result; <blockquote> Perturb 0.1704681 seconds for 382 Perturb 0.9307034 seconds for 256 Perturb 0.932266 seconds for 1 Perturb 0.4896138 seconds for 257 Perturb 0.1541828 seconds for 999 Perturb 0.2222421 seconds for 555 Perturb 0.2370868 seconds for 412 Perturb 0.2229154 seconds for 341 Perturb 0.2233445 seconds for 682 Perturb 0.1554396 seconds for 951 FastPerturb 0.2988974 seconds for 382 FastPerturb 1.8008209 seconds for 256 FastPerturb 1.7966043 seconds for 1 FastPerturb 0.9255025 seconds for 257 FastPerturb 0.2708695 seconds for 999 FastPerturb 0.4036553 seconds for 555 FastPerturb 0.401872 seconds for 412 FastPerturb 0.4042984 seconds for 341 FastPerturb 0.4028209 seconds for 682 FastPerturb 0.2688467 seconds for 951 SetRandomTrueBitToFalse 0.6127648 seconds for 382 SetRandomTrueBitToFalse 0.4432519 seconds for 256 SetRandomTrueBitToFalse 0.4193295 seconds for 1 SetRandomTrueBitToFalse 0.4543657 seconds for 257 SetRandomTrueBitToFalse 0.6270696 seconds for 999 SetRandomTrueBitToFalse 0.5891294 seconds for 555 SetRandomTrueBitToFalse 0.5910375 seconds for 412 SetRandomTrueBitToFalse 0.6104247 seconds for 341 SetRandomTrueBitToFalse 0.6249519 seconds for 682 SetRandomTrueBitToFalse 0.6142904 seconds for 951 flipRandomBit 0.1624584 seconds for 382 flipRandomBit 0.1284565 seconds for 256 flipRandomBit 0.13208 seconds for 1 flipRandomBit 0.1383649 seconds for 257 flipRandomBit 0.1658636 seconds for 999 flipRandomBit 0.1563506 seconds for 555 flipRandomBit 0.1588513 seconds for 412 flipRandomBit 0.1561841 seconds for 341 flipRandomBit 0.1562256 seconds for 682 flipRandomBit 0.167605 seconds for 951 oneBitsIndexes 2.1871352 seconds for 382 oneBitsIndexes 1.8677352 seconds for 256 oneBitsIndexes 1.8389871 seconds for 1 oneBitsIndexes 1.8729746 seconds for 257 oneBitsIndexes 2.1821771 seconds for 999 oneBitsIndexes 2.1300304 seconds for 555 oneBitsIndexes 2.1098191 seconds for 412 oneBitsIndexes 2.0836421 seconds for 341 oneBitsIndexes 2.0803612 seconds for 682 oneBitsIndexes 2.1684378 seconds for 951 ClearOneBit 0.3005068 seconds for 382 ClearOneBit 1.7872318 seconds for 256 ClearOneBit 1.7902597 seconds for 1 ClearOneBit 0.9243212 seconds for 257 ClearOneBit 0.2666008 seconds for 999 ClearOneBit 0.3929297 seconds for 555 ClearOneBit 0.3964557 seconds for 412 ClearOneBit 0.3945432 seconds for 341 ClearOneBit 0.3936286 seconds for 682 ClearOneBit 0.2686803 seconds for 951 FlipRandomTrueBit 1.5828644 seconds for 382 FlipRandomTrueBit 1.3162437 seconds for 256 FlipRandomTrueBit 1.2944724 seconds for 1 FlipRandomTrueBit 1.3305612 seconds for 257 FlipRandomTrueBit 1.5845461 seconds for 999 FlipRandomTrueBit 1.5252726 seconds for 555 FlipRandomTrueBit 1.5786568 seconds for 412 FlipRandomTrueBit 1.5314749 seconds for 341 FlipRandomTrueBit 1.5311035 seconds for 682 FlipRandomTrueBit 1.6164142 seconds for 951 ClearRandomBit 0.2681578 seconds for 382 ClearRandomBit 0.2728117 seconds for 256 ClearRandomBit 0.2685423 seconds for 1 ClearRandomBit 0.2626029 seconds for 257 ClearRandomBit 0.2623253 seconds for 999 ClearRandomBit 0.274382 seconds for 555 ClearRandomBit 0.2644288 seconds for 412 ClearRandomBit 0.2667171 seconds for 341 ClearRandomBit 0.264912 seconds for 682 ClearRandomBit 0.2666491 seconds for 951 </blockquote> so in the end, Kyteland is now the winner.
Tags
<c#><.net><vb.net><bit-manipulation>
Title
How do you randomly zero a bit in an integer?
singulars
PostAcceptedAnswerId
1. PO
 singulars
 PostTypePostTypeId
 PTAnswer
PostParentId
1. This table or related slice is empty.
PostTypePostTypeId
1. PTQuestion
UserLastEditorUserId
1. USFredou
UserOwnerUserId
1. USFredou
plurals
PostLinksPostIdRelatedPostId
1. This table or related slice is empty.
PostLinksRelatedPostIdPostId
1. This table or related slice is empty.
PostsAcceptedAnswerId
1. This table or related slice is empty.
PostsParentIdCreationDate
1. PO
 singulars
 PostTypePostTypeId
 PTAnswer
2. PO
 singulars
 PostTypePostTypeId
 PTAnswer
3. PO
 singulars
 PostTypePostTypeId
 PTAnswer
VotesPostIdCreationDate
1. VO
 singulars
 PostPostId
 POHow do you randomly zero a bit in an integer?
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
2. VO
 singulars
 PostPostId
 POHow do you randomly zero a bit in an integer?
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
3. VO
 singulars
 PostPostId
 POHow do you randomly zero a bit in an integer?
 UserUserId
 USJohn Feminella
 VoteTypeVoteTypeId
 VTFavorite
CommentsPostId

Querying!

Guidance

A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.