Come si azzera a caso un bit in un numero intero?

Question

Aggiornato con risposta più recente e migliore prova

Diciamo che ho il numero 382, ​​che è 101111110.

Come potrei casualmente girare un po 'che non è 0 a 0?

Il perché;

Poiché la gente mi chiede perché, ho semplicemente bisogno di farlo, rimuovendo un po 'da un numero intero.

in base alla risposta qui è il risultato (che lavora uno)
mi sono imbattuto questo risultato

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)); 
     } 
    } 
} 

;

perturbare 0.1704681 secondi per 382
perturbare 0.9307034 secondi per 256
perturbare 0.932266 secondi per 1
perturbare 0.4896138 secondi per 257
perturbare 0.1541828 secondi per 999
perturbare 0.2222421 secondi per 555
perturbare 0,2370,868 mila secondi per 412
Perturb 0.2229154 secondi per 341
Perturb 0.2233445 secondi per 682
perturbare 0.1554396 secondi per 951
FastPerturb 0.2988974 secondi per 382
FastPerturb 1.8008209 secondi per 256
FastPerturb 1,7966,043 mila secondo per 1
FastPerturb 0,9255,025 mila secondo per 257
FastPerturb ,2708,695 mila secondo per 999
FastPerturb 0,4036,553 mila secondo per 555
FastPerturb 0.401872 secondi per 412
FastPerturb 0.4042984 secondi per 341
FastPerturb 0.4028209 secondi per 682
FastPerturb 0.2688467 secondi per 951
SetRandomTrueBitToFalse 0.6127648 secondi per 382
SetRandomTrueBitToFalse 0,4432,519 mila secondo per 256
SetRandomTrueBitToFalse 0,4193,295 mila secondo per 1
SetRandomTrueBitToFalse 0,4543,657 mila secondo per 257
SetRandomTrueBitToFalse ,6270,696 mila secondo per 999
SetRandomTrueBitToFalse 0,5891,294 mila secondo per 555
SetRandomTrueBitToFalse 0.5910375 secondi per 412
SetRandomTrueBitToFalse 0.6104247 secondi per 341
S etRandomTrueBitToFalse 0.6249519 secondi per 682
SetRandomTrueBitToFalse 0,6142,904 mila secondo per 951
flipRandomBit 0,1624,584 mila secondo per 382
flipRandomBit 0,1284,565 mila secondo per 256
flipRandomBit 0,13,208 mila secondo per 1
flipRandomBit 0.1383649 secondi per 257
flipRandomBit 0.1658636 secondi per 999
flipRandomBit 0.1563506 secondi per 555
flipRandomBit 0,1588,513 mila secondo per 412
flipRandomBit 0,1561,841 mila secondo per 341
flipRandomBit 0,1562,256 mila secondo per 682
flipRandomBit 0,167,605 mila secondo per 951
oneBitsIndexes 2,1871,352 mila secondi per 382
oneBitsIndexes 1.8677352 secondi per 256
oneBitsIndexes 1.8389871 secondi per 1
oneBit sIndexes 1.8729746 secondi per 257
oneBitsIndexes 2,1821,771 mila secondo per 999
oneBitsIndexes 2,1300,304 mila secondo per 555
oneBitsIndexes 2,1098,191 mila secondo per 412
oneBitsIndexes 2,0836,421 mila secondo per 341
oneBitsIndexes 2,0803,612 mila secondo per 682
oneBitsIndexes 2,1684,378 mila secondo per 951
ClearOneBit 0,3005068 secondi per 382
ClearOneBit 1.7872318 secondi per 256
ClearOneBit 1.7902597 secondi per 1
ClearOneBit 0.9243212 secondi per 257
ClearOneBit 0.2666008 secondi per 999
ClearOneBit 0.3929297 secondi per 555
ClearOneBit 0,3964,557 mila secondo per 412
ClearOneBit 0,3945,432 mila secondo per 341
ClearOneBit 0,3936,286 mila secondo per 682
ClearOneBit 0,2686,803 mila secondo per 951
FlipRandomTrueBit 1.5828644 secondi per 382
FlipRandomTrueBit 1.3162437 secondi per 256
FlipRandomTrueBit 1,2944,724 mila secondo per 1
FlipRandomTrueBit 1.3305612 secondi per 257
FlipRandomTrueBit 1.5845461 secondi per 999
FlipRandomTrueBit 1.5252726 secondi per 555
FlipRandomTrueBit 1.5786568 secondi per 412
FlipRandomTrueBit 1.5314749 secondi per 341
FlipRandomTrueBit 1.5311035 secondi per 682
FlipRandomTrueBit 1.6164142 secondi per 951
ClearRandomBit 0,2681578 secondi per 382
ClearRandomBit 0,2728117 secondi per 256
ClearRandomBit 0,2685423 secondi per 1
ClearRandomBit 0.2626029 secondi per 257
ClearRandomBit 0.2623253 secondi per 999
ClearRandomBit 0.274382 secondi per 555
ClearRandomBit 0,2644,288 mila secondo per 412
ClearRandomBit 0,2667,171 mila secondo per 341
ClearRandomBit 0,264,912 mila secondo per 682
ClearRandomBit 0.2666491 secondi per 951

quindi, alla fine, Kyteland è ora il vincitore.

Answer 1

Ecco una versione leggermente più efficiente che utilizza il bit twiddling.

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; 
    } 

Answer 2

EDIT: fissato tenendo conto del vincolo "un bit che non è 0"

Scegliere un numero casuale N tra 0 e 31 (per un intero a 32 bit), e usarlo per generare un maschera di bit spostando 1 N volte a sinistra. Ripeti fino a quando il bit N non è 0 nel numero originale. Negare la maschera di bit di avere solo 1 bit impostato a 0 e si combinano con il vostro numero originale con il & dell'operatore:

private int ClearOneBit(int originalValue) 
{ 
    if (originalValue == 0) 
     return 0; // All bits are already set to 0, nothing to do 

    Random rnd = new Random(); 
    int mask = 0; 
    do 
    { 
     int n = rnd.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; 
} 

Answer 3

è possibile attivare qualsiasi bit per OR'ing con 1 e spegnerlo da E' con il complemento bit a bit.

Ecco un esempio che seleziona un 1 bit casuale e lo spegne.

var rand = new Random(); 
int myValue = 0x017E; // 101111110b 
// identify which indexes are one-bits (if any, thanks Doc) 
if(myValue > 0) 
{ 
    var oneBitsIndexes = Enumerable.Range(0, 31) 
            .Where(i => ((myValue >> i) & 0x1) !=0).ToList(); 
    // pick a random index and update the source value bit there from 1 to 0 
    myValue &= ~(1 << oneBitsIndexes[rand.Next(oneBitsIndexes.Count)]); 
} 
// otherwise, there are no bits to turn off... 

Answer 4

provare il seguente codice

public static int ChangeOneBit(int data) 
{ 
    if (data == 0) 
    { 
     return data; 
    } 

    var random = new Random(); 
    int bit = 0; 
    do 
    { 
     var shift = random.Next(31); 
     bit = data >> shift; 
     bit = bit & 0x00000001; 
    } while (bit == 0); 
    var ret = data & (~(1 << bit)); 
    return ret; 
} 

Answer 5

EDIT: Fissa una certa logica.

BitArray bits = new BitArray(new int[] { number }); 

randomIndex = new Random().Next(32); 

// check if bit is true, if not, goes to next bit and wraps around as well. 
for(int i = 0; i < 32; i++) 
{ 
    if(bits[randomIndex] == false) 
    { 
    randomIndex = (randomIndex + 1) % 32; 
    } 
    else 
    { 
     break; 
    } 
} 

bits[randomIndex] = false; 

Answer 6

Contare tutti i numeri 1 nel numero intero. Scegli un numero casuale usando il tuo generatore di numeri casuali preferiti tra 1 e il primo conteggio. Crea una maschera per Random-th 1 nel tuo numero intero. OPPURE il numero intero con la maschera.

Answer 7

int changeBit(int a) 
{ 
    a = ~a; 
    int temp = a; 
    while(temp == a) 
    { 
     r = Math.pow(2,(int)(32*random.next())); 
     a = a || r;  
    } 

    return ~a; 
} 

Answer 8

static Random random = new Random(); 

public static int Perturb(int data) 
{ 
    if (data == 0) return 0; 

    // attempt to pick a more narrow search space 
    int minBits = (data & 0xFFFF0000) == 0 ? 16 : 32; 

    // int used = 0; // Uncomment for more-bounded performance 
    int newData = data; 
    do 
    { 
     // Unbounded performance guarantees 
     newData &= ~(1 << random.Next(minBits)); 

     // // More-bounded performance: 
     // int bit = 1 << random.Next(minBits); 
     // if ((used & bit) == bit) continue; 
     // used |= bit; 
     // newData &= ~bit; 
    } while (newData == data); // XXX: we know we've inverted at least one 1 
           // when the new value differs 

    return newData; 
} 

Aggiornamento: codice aggiunto di sopra del quale possono essere utilizzati per le garanzie maggiori-delimitata prestazioni (o meno illimitata se si vuole pensare in questo modo). È interessante notare come questo funzioni meglio della versione originale non commentata.

Di seguito è un approccio alternativo che è veloce ma senza garanzie di prestazioni limitate:

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; 
} 

Answer 9

Ok, un sacco di risposte sbagliate. Ecco uno che funziona:

1. determinare quale bit da capovolgere. Fallo casualmente Non fornirò il codice, è piuttosto semplice.
2. impostare una maschera di bit con tutti gli zeri, con 1 per il bit in questione. Ad esempio, se è il 3 ° bit, la tua maschera di bit potrebbe essere 00000100. Di nuovo, questo non richiede codice.
3. bit a bit XOR il numero con la maschera bit. Se non si ha familiarità con l'operatore è l'operatore di cappello: ^

Ecco alcuni esempi di codice:

int myInt; // set this up with your original value 
int myBitmask; // set this up with the bit mask via steps 1 and 2. 
int randomlyZeroedBitInt = myInt^myBitmask; 

Edit: Su una quinta lettura della questione, ho una domanda in cambio : si vogliono fare, che delle operazioni seguenti:

1. casualmente azzerare un po ', ma solo se tale bit è già 1. in altre parole, se il bit in questione non è già 1, l'operazione è un non-op.
2. Scegliere a caso un bit che è 1 e azzerarlo. Questa operazione sceglie sempre un bit che è già 1 e sempre lo zero. L'operazione è solo un no-op se il valore originale è 0.

Edit 2:

2 è corretta, (15chars) - fredou

In tal caso , il mio algoritmo generale sta; semplicemente scegliere il bit nel passaggio 1 con la logica interna. In alternativa, scegliere un bit completamente casuale nel passaggio 1 e ripetere finché il valore di myInt e randomlyZeroedBitInt non sono uguali.

Sfortunatamente, in entrambi i casi si intende un algoritmo più complesso, in quanto è necessario eseguire un'iterazione su ogni bit del valore per determinare quale di essi capovolgere, oppure è necessario eseguire il ciclo dell'algoritmo fino a quando un bit non viene capovolto.

Answer 10

OK:

private static Random rnd = new Random((int)DateTime.Now.Ticks); 

    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 = rnd.Next(0, trueBits.Count); 
      return p & ~(1 << trueBits[index]); 
     } 
     return p; 
    } 

Ma mi piacerebbe sapere: Perché avete bisogno/vuole questo?

Answer 11

int val=382 

int mask = ~(1 << N) 

// this would turn-off nth bit (0 to 31) 
NewVal = (int) ((uint)val & (uint)mask} 

Answer 12

È possibile generalizzare utilizzando BitArray.

Tuttavia, sarà necessario scrivere funzioni di supporto per tipi di dati semplici.

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; 
} 

Se si utilizza un array di bit di grandi dimensioni è possibile risparmiare memoria ripetendo due volte.

public static void FlipRandomTrueBitLowMem(ref BitArray bits) 
{ 
    int trueBits = 0; 

    for (int i = 0; i < bits.Count; i++) 
     if (bits[i]) 
      trueBits++; 

    if (trueBits > 0) 
    { 
     int flip = rnd.Next(0, trueBits); 

     for (int i = 0; i < bits.Count; i++) 
     { 
      if (bits[i]) 
      { 
       if (flip == 0) 
       { 
        bits[i] = false; 
        break; 
       } 

       flip--; 
      } 
     } 
    } 
} 

Programma di test.

using System; 
using System.Collections; 
using System.Collections.Generic; 
using System.Linq; 

namespace bitarray 
{ 
    class Program 
    { 
     private static Random rnd = new Random((int)DateTime.Now.Ticks); 

     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 = rnd.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 void Main(string[] args) 
     { 
      int test = 382; 
      for (int n = 0; n < 200; n++) 
      { 
       int result = FlipRandomTrueBit(test); 
       Console.WriteLine(result); 
      } 

      Console.ReadLine(); 
     } 
    } 
} 

Answer 13

Ecco una versione basata su un algorithm da Bit Twiddling Hacks per selezionare il bit insieme n-esima di un intero. Per questo caso, selezioniamo semplicemente n a caso.

Il codice è stato portato su C#, realizzato per funzionare direttamente su interi con segno a 32 bit e conteggio a destra invece che a sinistra. Inoltre, l'ottimizzazione per rimuovere tutti i rami non è stata conservata qui in quanto ha prodotto un codice più lento sulla mia macchina (Intel Core 2 Quad Q9450).

La descrizione nella pagina Bit Twiddling Hacks non fornisce molte informazioni sul funzionamento dell'algoritmo. Mi sono preso il tempo di farlo e di decodificarlo e ciò che ho trovato è descritto in dettaglio nei commenti seguenti.

Nei miei test, questo algoritmo si comporta in modo molto simile all'eccellente flipRandomBit di Kyteland su un input distribuito in modo casuale nell'intero intervallo di numeri interi a 32 bit. Tuttavia, flipRandomBit è leggermente più veloce per i numeri con un numero di bit di impostazione significativamente inferiore rispetto ai bit cancellati. Viceversa, questo algoritmo è leggermente più veloce per i numeri con un numero significativamente maggiore di bit impostati rispetto ai bit cancellati.

Il benchmark dell'OP è costituito interamente da piccoli numeri interi positivi, che non mettono in evidenza il caso peggiore di flipRandomBit. Se questa è un'indicazione dell'ingresso atteso, allora un motivo in più per preferire flipRandomBit.

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 >> 1) & m2); 

    // sequence of 4-bit values representing the counts of each 4 bits. 
    int c4 = (c2 & m4) + ((c2 >> 2) & m4); 

    // sequence of 8-bit values representing the counts of each 8 bits. 
    int c8 = (c4 + (c4 >> 4)) & m8; 

    // count set bits in input. 
    int bitCount = (c8 * 0x1010101) >> 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 >> 8)) & 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 > count) { pos += 16; distance -= count; } 

    // if the target is not in the next 8 bits, move past them 
    count = (c8 >> pos) & 0xff; 
    if (distance > count) { pos += 8; distance -= count; } 

    // if the target is not in the next 4 bits, move past them 
    count = (c4 >> pos) & 0xf; 
    if (distance > count) { pos += 4; distance -= count; } 

    // if the target is not in the next 2 bits, move past them 
    count = (c2 >> pos) & 0x3; 
    if (distance > 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 & 0x1) == distance); 
    Debug.Assert((count & 0x1) == count); 
    count = (input >> pos) & 0x1; 
    pos += (distance & (count^1)); 

    Debug.Assert((input & (1 << pos)) != 0); 
    return input^(1 << pos); 
}