如何将整数中的位随机置零？
使用更新的答案和更好的测试更新了
假设我有数字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秒
1的扰动时间为0.932266秒
扰动0.4896138秒，持续257秒
扰动0.1541828秒持续999
扰动0.2222421秒持续555秒
扰动0.2370868秒412秒
341的扰动0.2229154秒
扰动0.2233445秒682
微扰0.1554396秒951
382的FastPerturb 0.2988974秒
FastPerturb 1.8008209秒，共256
%1的FastPerturb 1.7966043秒
257的FastPerturb 0.9255025秒
999的FastPerturb 0.2708695秒
555的FastPerturb为0.4036553秒
412秒的FastPerturb 0.401872秒
341的FastPerturb 0.4042984秒
682的FastPerturb 0.4028209秒
951的FastPerturb 0.2688467秒
382的SetRandomTrueBitToFalse 0.6127648秒
SetRandomTrueBitToFalse 0.4432519秒，共256
%1的SetRandomTrueBitToFalse 0.4193295秒
257的SetRandomTrueBitToFalse 0.4543657秒
999的SetRandomTrueBitToFalse 0.6270696秒
555的SetRandomTrueBitToFalse为0.5891294秒
412秒的SetRandomTrueBitToFalse 0.5910375秒
341的SetRandomTrueBitToFalse 0.6104247秒
682的SetRandomTrueBitToFalse 0.6249519秒
951的SetRandomTrueBitToFalse 0.6142904秒
382的flipRandomBit 0.1624584秒
flipRandomBit 0.1284565秒，共256
%1的flipRandomBit 0.13208秒
257的flipRandomBit 0.1383649秒
999的flipRandomBit 0.1658636秒
555的flipRandomBit为0.1563506秒
412秒的flipRandomBit 0.1588513秒
341的flipRandomBit 0.1561841秒
682的flipRandomBit 0.1562256秒
951的flipRandomBit 0.167605秒
382的oneBitsIndexes 2.1871352秒
oneBitsIndexes 1.8677352秒，共256
%1的oneBitsIndexes 1.8389871秒
257的oneBitsIndexes 1.8729746秒
999的oneBitsIndexes 2.1821771秒
555的oneBitsIndexes为2.1300304秒
412秒的oneBitsIndexes 2.1098191秒
341的oneBitsIndexes 2.0836421秒
682的oneBitsIndexes 2.0803612秒
951的oneBitsIndexes 2.1684378秒
382的ClearOneBit 0.3005068秒
ClearOneBit 1.7872318秒，共256
%1的ClearOneBit 1.7902597秒
257的ClearOneBit 0.9243212秒
999的ClearOneBit 0.2666008秒
555的ClearOneBit为0.3929297秒
412秒的ClearOneBit 0.3964557秒
341的ClearOneBit 0.3945432秒
682的ClearOneBit 0.3936286秒
951的ClearOneBit 0.2686803秒
382的FlipRandomTrueBit 1.5828644秒
FlipRandomTrueBit 1.3162437秒，共256
%1的FlipRandomTrueBit 1.2944724秒
257的FlipRandomTrueBit 1.3305612秒
999的FlipRandomTrueBit 1.5845461秒
555的FlipRandomTrueBit为1.5252726秒
412秒的FlipRandomTrueBit 1.5786568秒
341的FlipRandomTrueBit 1.5314749秒
682的FlipRandomTrueBit 1.5311035秒
951的FlipRandomTrueBit 1.6164142秒
382的ClearRandomBit 0.2681578秒
ClearRandomBit 0.2728117秒，共256
%1的ClearRandomBit 0.2685423秒
257的ClearRandomBit 0.2626029秒
999的ClearRandomBit 0.2623253秒
555的ClearRandomBit为0.274382秒
412秒的ClearRandomBit 0.2644288秒
341的ClearRandomBit 0.2667171秒
682的ClearRandomBit 0.264912秒
ClearRandomBit 0.2666491秒，适用于951
所以最终，Kyteland现在是胜利者。
回答 13
Stack Overflow用户
发布于 2010-01-06 09:26:51
这是一个使用位旋转的更有效的版本。
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;
}Stack Overflow用户
发布于 2010-01-05 03:49:37
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;
}Stack Overflow用户
发布于 2010-01-05 03:35:47
EDIT :已修复，以考虑约束条件"a bit is not is not 0“
选择0到31之间的一个随机数N(对于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;
}https://stackoverflow.com/questions/2001597
复制相似问题
腾讯云开发者
