title: How do you randomly zero a bit in an integer?
body: <p><strong>Updated with newer answer and better test</strong></p>
  
  <p>Let's say I have the number 382 which is 101111110.</p>
  
  <p>How could I randomly turn a bit which is not 0 to 0?</p>
  
  <p>The why;</p>
  
  <p>Since people ask me why, I simply need to do this, removing a bit from an integer.</p>
  
  <p>based on the answer here is the result(working one)<br>
  I ran this   </p>
  
  <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 &lt; 10; j++)
              {
                  sw = Stopwatch.StartNew();
                  for (int i = 0; i &lt; 1000000; i++)
                      Perturb(test[j]);
                  sw.Stop();
                  Console.WriteLine("Perturb " + sw.Elapsed.TotalSeconds.ToString("0.#######") + " seconds for " + test[j].ToString());
                  Debug.WriteLine("&gt; Perturb " + sw.Elapsed.TotalSeconds.ToString("0.#######") + " seconds for " + test[j].ToString() + "  ");
              }
  
              random = new Random(42);
              for (int j = 0; j &lt; 10; j++)
              {
                  sw = Stopwatch.StartNew();
                  for (int i = 0; i &lt; 1000000; i++)
                      FastPerturb(test[j]);
                  sw.Stop();
                  Console.WriteLine("FastPerturb " + sw.Elapsed.TotalSeconds.ToString("0.#######") + " seconds for " + test[j].ToString());
                  Debug.WriteLine("&gt; FastPerturb " + sw.Elapsed.TotalSeconds.ToString("0.#######") + " seconds for " + test[j].ToString() + "  ");
              }
  
              random = new Random(42);
              for (int j = 0; j &lt; 10; j++)
              {
                  sw = Stopwatch.StartNew();
                  for (int i = 0; i &lt; 1000000; i++)
                      SetRandomTrueBitToFalse(test[j]);
                  sw.Stop();
                  Console.WriteLine("SetRandomTrueBitToFalse " + sw.Elapsed.TotalSeconds.ToString("0.#######") + " seconds for " + test[j].ToString());
                  Debug.WriteLine("&gt; SetRandomTrueBitToFalse " + sw.Elapsed.TotalSeconds.ToString("0.#######") + " seconds for " + test[j].ToString() + "  ");
              }
  
              random = new Random(42);
              for (int j = 0; j &lt; 10; j++)
              {
                  sw = Stopwatch.StartNew();
                  for (int i = 0; i &lt; 1000000; i++)
                      flipRandomBit(test[j]);
                  sw.Stop();
                  Console.WriteLine("flipRandomBit " + sw.Elapsed.TotalSeconds.ToString("0.#######") + " seconds for " + test[j].ToString());
                  Debug.WriteLine("&gt; flipRandomBit " + sw.Elapsed.TotalSeconds.ToString("0.#######") + " seconds for " + test[j].ToString() + "  ");
              }
  
              random = new Random(42);
              for (int j = 0; j &lt; 10; j++)
              {
                  sw = Stopwatch.StartNew();
                  for (int i = 0; i &lt; 1000000; i++)
                      oneBitsIndexes(test[j]);
                  sw.Stop();
                  Console.WriteLine("oneBitsIndexes " + sw.Elapsed.TotalSeconds.ToString("0.#######") + " seconds for " + test[j].ToString());
                  Debug.WriteLine("&gt; oneBitsIndexes " + sw.Elapsed.TotalSeconds.ToString("0.#######") + " seconds for " + test[j].ToString() + "  ");
              }
  
              random = new Random(42);
              for (int j = 0; j &lt; 10; j++)
              {
                  sw = Stopwatch.StartNew();
                  for (int i = 0; i &lt; 1000000; i++)
                      ClearOneBit(test[j]);
                  sw.Stop();
                  Console.WriteLine("ClearOneBit " + sw.Elapsed.TotalSeconds.ToString("0.#######") + " seconds for " + test[j].ToString());
                  Debug.WriteLine("&gt; ClearOneBit " + sw.Elapsed.TotalSeconds.ToString("0.#######") + " seconds for " + test[j].ToString() + "  ");
              }
  
              random = new Random(42);
              for (int j = 0; j &lt; 10; j++)
              {
                  sw = Stopwatch.StartNew();
                  for (int i = 0; i &lt; 1000000; i++)
                      FlipRandomTrueBit(test[j]);
                  sw.Stop();
                  Console.WriteLine("FlipRandomTrueBit " + sw.Elapsed.TotalSeconds.ToString("0.#######") + " seconds for " + test[j].ToString());
                  Debug.WriteLine("&gt; FlipRandomTrueBit " + sw.Elapsed.TotalSeconds.ToString("0.#######") + " seconds for " + test[j].ToString() + "  ");
              }
  
              random = new Random(42);
              for (int j = 0; j &lt; 10; j++)
              {
                  sw = Stopwatch.StartNew();
                  for (int i = 0; i &lt; 1000000; i++)
                      ClearRandomBit(test[j]);
                  sw.Stop();
                  Console.WriteLine("ClearRandomBit " + sw.Elapsed.TotalSeconds.ToString("0.#######") + " seconds for " + test[j].ToString());
                  Debug.WriteLine("&gt; 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 &amp; 0xFFFF0000) == 0 ? 16 : 32;
  
              int newData = data;
              do
              {
                  newData &amp;= ~(1 &lt;&lt; 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 &amp; (bit = 1 &lt;&lt; random.Next(32)))) ;
  
              return data &amp; ~bit;
          }
  
          private static Int32 SetRandomTrueBitToFalse(Int32 p)
          {
              List&lt;int&gt; trueBits = new List&lt;int&gt;();
              for (int i = 0; i &lt; 31; i++)
              {
                  if ((p &gt;&gt; i &amp; 1) == 1)
                  {
                      trueBits.Add(i);
                  }
              }
              if (trueBits.Count &gt; 0)
              {
                  int index = random.Next(0, trueBits.Count);
                  return p &amp; ~(1 &lt;&lt; trueBits[index]);
              }
              return p;
          }
  
          public static int getBitCount(int bits)
          {
              bits = bits - ((bits &gt;&gt; 1) &amp; 0x55555555);
              bits = (bits &amp; 0x33333333) + ((bits &gt;&gt; 2) &amp; 0x33333333);
              return ((bits + (bits &gt;&gt; 4) &amp; 0xF0F0F0F) * 0x1010101) &gt;&gt; 24;
          }
  
          public static int flipRandomBit(int data)
          {
              int index = random.Next(getBitCount(data));
              int mask = data;
  
              for (int i = 0; i &lt; index; i++)
                  mask &amp;= mask - 1;
              mask ^= mask &amp; (mask - 1);
  
              return data ^ mask;
          }
  
          public static int oneBitsIndexes(int data)
          {
              if (data &gt; 0)
              {
                  var oneBitsIndexes = Enumerable.Range(0, 31)
                                                 .Where(i =&gt; ((data &gt;&gt; i) &amp; 0x1) != 0).ToList();
                  // pick a random index and update the source value bit there from 1 to 0
                  data &amp;= ~(1 &lt;&lt; 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 &lt;&lt; n;
              } while ((mask &amp; originalValue) == 0); // check that this bit is not 0
  
              int newValue = originalValue &amp; ~mask; // clear this bit
              return newValue;
          }
  
          public static BitArray FlipRandomTrueBit(BitArray bits)
          {
              List&lt;int&gt; trueBits = new List&lt;int&gt;();
  
              for (int i = 0; i &lt; bits.Count; i++)
                  if (bits[i])
                      trueBits.Add(i);
  
              if (trueBits.Count &gt; 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 &gt;&gt; 1) &amp; ~0UL / 3);
              ulong b = (a &amp; ~0UL / 5) + ((a &gt;&gt; 2) &amp; ~0UL / 5);
              ulong c = (b + (b &gt;&gt; 4)) &amp; ~0UL / 0x11;
              ulong d = (c + (c &gt;&gt; 8)) &amp; ~0UL / 0x101;
              ulong t = (uint)((d &gt;&gt; 32) + (d &gt;&gt; 48));
  
              // Choose a random r in the range [1-bitCount]
              int bitCount = (int)((d * (~0UL / 255)) &gt;&gt; 56);
              int randomRank = 1 + random.Next(bitCount);
              ulong r = (ulong)randomRank;
  
              // Compute s                                       
              ulong s = 64;
              s -= ((t - r) &amp; 256UL) &gt;&gt; 3;
              r -= (t &amp; ((t - r) &gt;&gt; 8));
              t = (d &gt;&gt; (int)(s - 16)) &amp; 0xff;
              s -= ((t - r) &amp; 256UL) &gt;&gt; 4;
              r -= (t &amp; ((t - r) &gt;&gt; 8));
              t = (c &gt;&gt; (int)(s - 8)) &amp; 0xf;
              s -= ((t - r) &amp; 256UL) &gt;&gt; 5;
              r -= (t &amp; ((t - r) &gt;&gt; 8));
              t = (b &gt;&gt; (int)(s - 4)) &amp; 0xf;
              s -= ((t - r) &amp; 256UL) &gt;&gt; 6;
              r -= (t &amp; ((t - r) &gt;&gt; 8));
              t = (a &gt;&gt; (int)(s - 2)) &amp; 0x3;
              s -= ((t - r) &amp; 256UL) &gt;&gt; 7;
              r -= (t &amp; ((t - r) &gt;&gt; 8));
              t = (v &gt;&gt; (int)(s - 1)) &amp; 0x1;
              s -= ((t - r) &amp; 256UL) &gt;&gt; 8;
              s = 65 - s;
  
              // Clear the selected bit
              return value &amp; ~(1UL &lt;&lt; (int)(64 - s));
          }
      }
  }
  </code></pre>
  
  <p>result;</p>
  
  <blockquote>
    <p>Perturb 0.1704681 seconds for 382<br>
    Perturb 0.9307034 seconds for 256<br>
    Perturb 0.932266 seconds for 1<br>
    Perturb 0.4896138 seconds for 257<br>
    Perturb 0.1541828 seconds for 999<br>
    Perturb 0.2222421 seconds for 555<br>
    Perturb 0.2370868 seconds for 412<br>
    Perturb 0.2229154 seconds for 341<br>
    Perturb 0.2233445 seconds for 682<br>
    Perturb 0.1554396 seconds for 951<br>
    FastPerturb 0.2988974 seconds for 382<br>
    FastPerturb 1.8008209 seconds for 256<br>
    FastPerturb 1.7966043 seconds for 1<br>
    FastPerturb 0.9255025 seconds for 257<br>
    FastPerturb 0.2708695 seconds for 999<br>
    FastPerturb 0.4036553 seconds for 555<br>
    FastPerturb 0.401872 seconds for 412<br>
    FastPerturb 0.4042984 seconds for 341<br>
    FastPerturb 0.4028209 seconds for 682<br>
    FastPerturb 0.2688467 seconds for 951<br>
    SetRandomTrueBitToFalse 0.6127648 seconds for 382<br>
    SetRandomTrueBitToFalse 0.4432519 seconds for 256<br>
    SetRandomTrueBitToFalse 0.4193295 seconds for 1<br>
    SetRandomTrueBitToFalse 0.4543657 seconds for 257<br>
    SetRandomTrueBitToFalse 0.6270696 seconds for 999<br>
    SetRandomTrueBitToFalse 0.5891294 seconds for 555<br>
    SetRandomTrueBitToFalse 0.5910375 seconds for 412<br>
    SetRandomTrueBitToFalse 0.6104247 seconds for 341<br>
    SetRandomTrueBitToFalse 0.6249519 seconds for 682<br>
    SetRandomTrueBitToFalse 0.6142904 seconds for 951<br>
    flipRandomBit 0.1624584 seconds for 382<br>
    flipRandomBit 0.1284565 seconds for 256<br>
    flipRandomBit 0.13208 seconds for 1<br>
    flipRandomBit 0.1383649 seconds for 257<br>
    flipRandomBit 0.1658636 seconds for 999<br>
    flipRandomBit 0.1563506 seconds for 555<br>
    flipRandomBit 0.1588513 seconds for 412<br>
    flipRandomBit 0.1561841 seconds for 341<br>
    flipRandomBit 0.1562256 seconds for 682<br>
    flipRandomBit 0.167605 seconds for 951<br>
    oneBitsIndexes 2.1871352 seconds for 382<br>
    oneBitsIndexes 1.8677352 seconds for 256<br>
    oneBitsIndexes 1.8389871 seconds for 1<br>
    oneBitsIndexes 1.8729746 seconds for 257<br>
    oneBitsIndexes 2.1821771 seconds for 999<br>
    oneBitsIndexes 2.1300304 seconds for 555<br>
    oneBitsIndexes 2.1098191 seconds for 412<br>
    oneBitsIndexes 2.0836421 seconds for 341<br>
    oneBitsIndexes 2.0803612 seconds for 682<br>
    oneBitsIndexes 2.1684378 seconds for 951<br>
    ClearOneBit 0.3005068 seconds for 382<br>
    ClearOneBit 1.7872318 seconds for 256<br>
    ClearOneBit 1.7902597 seconds for 1<br>
    ClearOneBit 0.9243212 seconds for 257<br>
    ClearOneBit 0.2666008 seconds for 999<br>
    ClearOneBit 0.3929297 seconds for 555<br>
    ClearOneBit 0.3964557 seconds for 412<br>
    ClearOneBit 0.3945432 seconds for 341<br>
    ClearOneBit 0.3936286 seconds for 682<br>
    ClearOneBit 0.2686803 seconds for 951<br>
    FlipRandomTrueBit 1.5828644 seconds for 382<br>
    FlipRandomTrueBit 1.3162437 seconds for 256<br>
    FlipRandomTrueBit 1.2944724 seconds for 1<br>
    FlipRandomTrueBit 1.3305612 seconds for 257<br>
    FlipRandomTrueBit 1.5845461 seconds for 999<br>
    FlipRandomTrueBit 1.5252726 seconds for 555<br>
    FlipRandomTrueBit 1.5786568 seconds for 412<br>
    FlipRandomTrueBit 1.5314749 seconds for 341<br>
    FlipRandomTrueBit 1.5311035 seconds for 682<br>
    FlipRandomTrueBit 1.6164142 seconds for 951<br>
    ClearRandomBit 0.2681578 seconds for 382<br>
    ClearRandomBit 0.2728117 seconds for 256<br>
    ClearRandomBit 0.2685423 seconds for 1<br>
    ClearRandomBit 0.2626029 seconds for 257<br>
    ClearRandomBit 0.2623253 seconds for 999<br>
    ClearRandomBit 0.274382 seconds for 555<br>
    ClearRandomBit 0.2644288 seconds for 412<br>
    ClearRandomBit 0.2667171 seconds for 341<br>
    ClearRandomBit 0.264912 seconds for 682<br>
    ClearRandomBit 0.2666491 seconds for 951  </p>
  </blockquote>
  
  <p>so in the end, Kyteland is now the winner.</p>