Обновлен с более новым ответом и лучшим тестом
Скажем, у меня есть номер 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
Perturb 0.9307034 секунды для 256
Пертурб 0.932266 секунд для 1
Perturb 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 теперь побеждает.