问题描述
更新与新的答案和更好的测试
比方说，我有一些382是101111110。
Let's say I have the number 382 which is 101111110.
我怎么能随意转了一下这是不是0至0？
How could I randomly turn a bit which is not 0 to 0?
其所以然;
由于人们问我为什么，我只需要做到这一点，从一个整数去掉了一下。
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
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
FastPerturb0.2988974秒382
FastPerturb1.8008209秒256
FastPerturb1.7966043秒1
FastPerturb0.9255025秒为257
FastPerturb0.2708695秒999
FastPerturb0.4036553秒为555
FastPerturb0.401872秒为412
FastPerturb0.4042984秒为341
FastPerturb0.4028209秒为682
FastPerturb0.2688467秒为951
SetRandomTrueBitToFalse0.6127648秒382
SetRandomTrueBitToFalse0.4432519秒256
SetRandomTrueBitToFalse0.4193295秒1
SetRandomTrueBitToFalse0.4543657秒为257
SetRandomTrueBitToFalse0.6270696秒999
SetRandomTrueBitToFalse0.5891294秒为555
SetRandomTrueBitToFalse0.5910375秒为412
SetRandomTrueBitToFalse0.6104247秒为341
SetRandomTrueBitToFalse0.6249519秒为682
SetRandomTrueBitToFalse0.6142904秒为951
flipRandomBit0.1624584秒382
flipRandomBit0.1284565秒256
flipRandomBit0.13208秒1
flipRandomBit0.1383649秒为257
flipRandomBit0.1658636秒999
flipRandomBit0.1563506秒为555
flipRandomBit0.1588513秒为412
flipRandomBit0.1561841秒为341
flipRandomBit0.1562256秒为682
flipRandomBit0.167605秒为951
oneBitsIndexes2.1871352秒382
oneBitsIndexes1.8677352秒256
oneBitsIndexes1.8389871秒1
oneBitsIndexes1.8729746秒为257
oneBitsIndexes2.1821771秒999
oneBitsIndexes2.1300304秒为555
oneBitsIndexes2.1098191秒为412
oneBitsIndexes2.0836421秒为341
oneBitsIndexes2.0803612秒为682
oneBitsIndexes2.1684378秒为951
ClearOneBit0.3005068秒382
ClearOneBit1.7872318秒256
ClearOneBit1.7902597秒1
ClearOneBit0.9243212秒为257
ClearOneBit0.2666008秒999
ClearOneBit0.3929297秒为555
ClearOneBit0.3964557秒为412
ClearOneBit0.3945432秒为341
ClearOneBit0.3936286秒为682
ClearOneBit0.2686803秒为951
FlipRandomTrueBit1.5828644秒382
FlipRandomTrueBit1.3162437秒256
FlipRandomTrueBit1.2944724秒1
FlipRandomTrueBit1.3305612秒为257
FlipRandomTrueBit1.5845461秒999
FlipRandomTrueBit1.5252726秒为555
FlipRandomTrueBit1.5786568秒为412
FlipRandomTrueBit1.5314749秒为341
FlipRandomTrueBit1.5311035秒为682
FlipRandomTrueBit1.6164142秒为951
ClearRandomBit0.2681578秒382
ClearRandomBit0.2728117秒256
ClearRandomBit0.2685423秒1
ClearRandomBit0.2626029秒为257
ClearRandomBit0.2623253秒999
ClearRandomBit0.274382秒为555
ClearRandomBit0.2644288秒为412
ClearRandomBit0.2667171秒为341
ClearRandomBit0.264912秒为682
ClearRandomBit0.2666491秒为951
所以最后，Kyteland现在是赢家。
so in the end, Kyteland is now the winner.
推荐答案
下面是一个使用位操作稍微更有效的版本。
Here's a slightly more efficient version using 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;
}
这篇关于你如何随机瞄准一个整数位？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！