你如何随机瞄准一个整数位？ [英] How do you randomly zero a bit in an integer?
问题描述
更新与新的答案和更好的测试
比方说，我有一些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
Perturb 0.1704681 seconds for 382
Perturb 0.9307034 seconds for 256
Perturb 0.932266 seconds for 1
Perturb 0.4896138 seconds for 257
Perturb 0.1541828 seconds for 999
Perturb 0.2222421 seconds for 555
Perturb 0.2370868 seconds for 412
Perturb 0.2229154 seconds for 341
Perturb 0.2233445 seconds for 682
Perturb 0.1554396 seconds for 951
FastPerturb 0.2988974 seconds for 382
FastPerturb 1.8008209 seconds for 256
FastPerturb 1.7966043 seconds for 1
FastPerturb 0.9255025 seconds for 257
FastPerturb 0.2708695 seconds for 999
FastPerturb 0.4036553 seconds for 555
FastPerturb 0.401872 seconds for 412
FastPerturb 0.4042984 seconds for 341
FastPerturb 0.4028209 seconds for 682
FastPerturb 0.2688467 seconds for 951
SetRandomTrueBitToFalse 0.6127648 seconds for 382
SetRandomTrueBitToFalse 0.4432519 seconds for 256
SetRandomTrueBitToFalse 0.4193295 seconds for 1
SetRandomTrueBitToFalse 0.4543657 seconds for 257
SetRandomTrueBitToFalse 0.6270696 seconds for 999
SetRandomTrueBitToFalse 0.5891294 seconds for 555
SetRandomTrueBitToFalse 0.5910375 seconds for 412
SetRandomTrueBitToFalse 0.6104247 seconds for 341
SetRandomTrueBitToFalse 0.6249519 seconds for 682
SetRandomTrueBitToFalse 0.6142904 seconds for 951
flipRandomBit 0.1624584 seconds for 382
flipRandomBit 0.1284565 seconds for 256
flipRandomBit 0.13208 seconds for 1
flipRandomBit 0.1383649 seconds for 257
flipRandomBit 0.1658636 seconds for 999
flipRandomBit 0.1563506 seconds for 555
flipRandomBit 0.1588513 seconds for 412
flipRandomBit 0.1561841 seconds for 341
flipRandomBit 0.1562256 seconds for 682
flipRandomBit 0.167605 seconds for 951
oneBitsIndexes 2.1871352 seconds for 382
oneBitsIndexes 1.8677352 seconds for 256
oneBitsIndexes 1.8389871 seconds for 1
oneBitsIndexes 1.8729746 seconds for 257
oneBitsIndexes 2.1821771 seconds for 999
oneBitsIndexes 2.1300304 seconds for 555
oneBitsIndexes 2.1098191 seconds for 412
oneBitsIndexes 2.0836421 seconds for 341
oneBitsIndexes 2.0803612 seconds for 682
oneBitsIndexes 2.1684378 seconds for 951
ClearOneBit 0.3005068 seconds for 382
ClearOneBit 1.7872318 seconds for 256
ClearOneBit 1.7902597 seconds for 1
ClearOneBit 0.9243212 seconds for 257
ClearOneBit 0.2666008 seconds for 999
ClearOneBit 0.3929297 seconds for 555
ClearOneBit 0.3964557 seconds for 412
ClearOneBit 0.3945432 seconds for 341
ClearOneBit 0.3936286 seconds for 682
ClearOneBit 0.2686803 seconds for 951
FlipRandomTrueBit 1.5828644 seconds for 382
FlipRandomTrueBit 1.3162437 seconds for 256
FlipRandomTrueBit 1.2944724 seconds for 1
FlipRandomTrueBit 1.3305612 seconds for 257
FlipRandomTrueBit 1.5845461 seconds for 999
FlipRandomTrueBit 1.5252726 seconds for 555
FlipRandomTrueBit 1.5786568 seconds for 412
FlipRandomTrueBit 1.5314749 seconds for 341
FlipRandomTrueBit 1.5311035 seconds for 682
FlipRandomTrueBit 1.6164142 seconds for 951
ClearRandomBit 0.2681578 seconds for 382
ClearRandomBit 0.2728117 seconds for 256
ClearRandomBit 0.2685423 seconds for 1
ClearRandomBit 0.2626029 seconds for 257
ClearRandomBit 0.2623253 seconds for 999
ClearRandomBit 0.274382 seconds for 555
ClearRandomBit 0.2644288 seconds for 412
ClearRandomBit 0.2667171 seconds for 341
ClearRandomBit 0.264912 seconds for 682
ClearRandomBit 0.2666491 seconds for 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;
}
这篇关于你如何随机瞄准一个整数位？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
