Как Вы случайным образом обнуляете немного в целом числе?
Обновленный с более новым ответом и лучшим тестом
Скажем, у меня есть номер 382, который является 101111110.
Как я мог случайным образом повернуться немного, который не является от 0 до 0?
Почему;
Так как люди спрашивают меня, почему, я просто должен сделать это, удалив немного из целого числа.
на основе ответа вот результат (работающий один)
Я выполнил это
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));
}
}
}
результат;
Встревожьте 0,1704681 секунды для 382
Встревожьте 0,9307034 секунды для 256
Встревожьте 0,932266 секунды для 1
Встревожьте 0,4896138 секунды для 257
Встревожьте 0,1541828 секунды для 999
Встревожьте 0,2222421 секунды для 555
Встревожьте 0,2370868 секунды для 412
Встревожьте 0,2229154 секунды для 341
Встревожьте 0,2233445 секунды для 682
Встревожьте 0,1554396 секунды для 951
Секунды FastPerturb 0.2988974 для 382
Секунды FastPerturb 1.8008209 для 256
Секунды FastPerturb 1.7966043 для 1
Секунды FastPerturb 0.9255025 для 257
Секунды FastPerturb 0.2708695 для 999
Секунды FastPerturb 0.4036553 для 555
Секунды FastPerturb 0.401872 для 412
Секунды FastPerturb 0.4042984 для 341
Секунды FastPerturb 0.4028209 для 682
Секунды FastPerturb 0.2688467 для 951
Секунды SetRandomTrueBitToFalse 0.6127648 для 382
Секунды SetRandomTrueBitToFalse 0.4432519 для 256
Секунды SetRandomTrueBitToFalse 0.4193295 для 1
Секунды SetRandomTrueBitToFalse 0.4543657 для 257
Секунды SetRandomTrueBitToFalse 0.6270696 для 999
Секунды SetRandomTrueBitToFalse 0.5891294 для 555
Секунды SetRandomTrueBitToFalse 0.5910375 для 412
Секунды SetRandomTrueBitToFalse 0.6104247 для 341
Секунды SetRandomTrueBitToFalse 0.6249519 для 682
Секунды SetRandomTrueBitToFalse 0.6142904 для 951
секунды flipRandomBit 0.1624584 для 382
секунды flipRandomBit 0.1284565 для 256
секунды flipRandomBit 0.13208 для 1
секунды flipRandomBit 0.1383649 для 257
секунды flipRandomBit 0.1658636 для 999
секунды flipRandomBit 0.1563506 для 555
секунды flipRandomBit 0.1588513 для 412
секунды flipRandomBit 0.1561841 для 341
секунды flipRandomBit 0.1562256 для 682
секунды flipRandomBit 0.167605 для 951
секунды oneBitsIndexes 2.1871352 для 382
секунды oneBitsIndexes 1.8677352 для 256
секунды oneBitsIndexes 1.8389871 для 1
секунды oneBitsIndexes 1.8729746 для 257
секунды oneBitsIndexes 2.1821771 для 999
секунды oneBitsIndexes 2.1300304 для 555
секунды oneBitsIndexes 2.1098191 для 412
секунды oneBitsIndexes 2.0836421 для 341
секунды oneBitsIndexes 2.0803612 для 682
секунды oneBitsIndexes 2.1684378 для 951
Секунды ClearOneBit 0.3005068 для 382
Секунды ClearOneBit 1.7872318 для 256
Секунды ClearOneBit 1.7902597 для 1
Секунды ClearOneBit 0.9243212 для 257
Секунды ClearOneBit 0.2666008 для 999
Секунды ClearOneBit 0.3929297 для 555
Секунды ClearOneBit 0.3964557 для 412
Секунды ClearOneBit 0.3945432 для 341
Секунды ClearOneBit 0.3936286 для 682
Секунды ClearOneBit 0.2686803 для 951
Секунды FlipRandomTrueBit 1.5828644 для 382
Секунды FlipRandomTrueBit 1.3162437 для 256
Секунды FlipRandomTrueBit 1.2944724 для 1
Секунды FlipRandomTrueBit 1.3305612 для 257
Секунды FlipRandomTrueBit 1.5845461 для 999
Секунды FlipRandomTrueBit 1.5252726 для 555
Секунды FlipRandomTrueBit 1.5786568 для 412
Секунды FlipRandomTrueBit 1.5314749 для 341
Секунды FlipRandomTrueBit 1.5311035 для 682
Секунды FlipRandomTrueBit 1.6164142 для 951
Секунды ClearRandomBit 0.2681578 для 382
Секунды ClearRandomBit 0.2728117 для 256
Секунды ClearRandomBit 0.2685423 для 1
Секунды ClearRandomBit 0.2626029 для 257
Секунды ClearRandomBit 0.2623253 для 999
Секунды ClearRandomBit 0.274382 для 555
Секунды ClearRandomBit 0.2644288 для 412
Секунды ClearRandomBit 0.2667171 для 341
Секунды ClearRandomBit 0.264912 для 682
Секунды ClearRandomBit 0.2666491 для 951
таким образом в конце, Kyteland является теперь победителем.
13 ответов
Вот немного более эффективная версия с использованием битового дёргивания.
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;
}
Вы можете включить любой бит с помощью оператора OR'ing с 1 и выключить его с помощью оператора AND'ing с битовым дополнением.
Вот пример, который выбирает случайный 1 бит и выключает его.
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...
Хорошо:
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;
}
Но я хотел бы знать: Зачем тебе это?
EDIT : исправлено для учета ограничения "бит, который не является 0"
Выберите случайное число N между 0 и 31 (для 32-битного целого числа) и используйте его для генерации битовой маски, сдвинув 1 N раз влево. Повторяйте до тех пор, пока бит N не станет не 0 в исходном числе. Отрицать битовую маску так, чтобы только 1 бит был равен 0, и объединять ее с исходным номером с помощью оператора & :
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;
}
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;
}
Обновление: добавлен код, выше которого можно использовать для более ограниченных гарантий производительности (или менее ограниченных, если вы хотите думать об этом таким образом). Интересно, что это работает лучше, чем оригинальная версия без комментариев.
Ниже приведен альтернативный подход, который является быстрым, но без ограниченных гарантий производительности:
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;
}
Считайте все 1 в вашем целочисленном. Выберите случайное число, используя любимый генератор случайных чисел между 1 и первым числом. Создайте маску для случайного числа 1 в вашем целом числе. ИЛИ целое число с маской.
int val=382
int mask = ~(1 << N)
// this would turn-off nth bit (0 to 31)
NewVal = (int) ((uint)val & (uint)mask}
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;
}
EDIT: Исправлена некоторая логика.
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;
Попробуйте следующий код
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;
}
Хорошо, много неправильных ответов. Вот один, который работает:
- определяет, какой бит переворачивать. Сделайте это случайным образом. Я не буду поставлять код, это довольно просто.
- установите битовую маску со всеми нулями, с 1 для рассматриваемого бита. Так, например, если это 3-й бит, то ваша битовая маска может быть 00000100. Опять же, для этого не нужен код.
- битовый XOR ваш номер с битовой маской. Если вы незнакомы с оператором, то это оператор шляпы:
^
Вот пример кода:
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;
Правка: На пятом чтении вопроса у меня в ответ возникает вопрос: Вы хотите сделать какой из следующих:
- Случайно нулевой бит, но только если этот бит уже 1. Другими словами, если бит, о котором идет речь, еще не 1, то операция будет нулевой.
- Случайно выбрать бит, равный 1, и обнулить его. Эта операция всегда выбирает бит, который уже 1, и всегда обнуляет его. Операция no-op только в том случае, если исходное значение равно 0.
Редактирование 2:
2 верно,(15chars) - Fredou
В этом случае мой общий алгоритм остается неизменным; достаточно выбрать бит на шаге 1 с внутренней логикой. Альтернативный вариант - выбрать полностью случайный бит на шаге 1 и повторять до тех пор, пока значения myInt и randomlyZeroedBitInt не будут равны.
К сожалению, любой случай означает более сложный алгоритм, так как для определения, какой из битов переворачивать, необходимо либо выполнить итерацию над каждым битом в вашем значении, либо зацикливать алгоритм до тех пор, пока бит не будет переворачиваться.
Вы можете обобщить это с помощью BitArray.
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;
}
Если вы используете большой битовый массив, то можете сохранить память, дважды выполнив итерацию.
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--;
}
}
}
}
Тестовая программа.
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();
}
}
}
Вот версия, основанная на алгоритме из Bit Twiddling Hacks для выбора n-го бита множества целого. В данном случае мы просто случайным образом выбираем n.
Код был перенесен на C#, чтобы работать непосредственно на 32-битных подписанных целых числах и считать справа, а не слева. Более того, здесь не сохранилась оптимизация по удалению всех веток, так как она дала более медленный код на моей машине (Intel Core 2 Quad Q9450).
Описание на странице Bit Twiddling Hacks не дает большого представления о том, как работает алгоритм. Я потратил время на то, чтобы пройтись по нему и переконструировать его, а то, что я нашел, подробно описано в комментариях ниже.
В моих тестах этот алгоритм работает очень похоже на отличный flipRandomBit Кайтланда над входом, который случайным образом распределяется по всему диапазону 32-битных целых чисел. Однако flipRandomBit немного быстрее для чисел со значительно меньшим количеством заданных битов, чем очищенные биты. И наоборот, данный алгоритм немного быстрее для чисел со значительно большим количеством заданных битов, чем очищенных.
ОП полностью состоит из маленьких положительных целых чисел, которые не подчеркивают худший случай flipRandomBit. Если это является признаком ожидаемого входа, то тем более стоит предпочесть 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);
}