你如何在整数中随机归零？

更新了更新的答案和更好的测试

假设我的号码是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  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  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  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  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  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  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  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  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 trueBits = new List(); for (int i = 0; i > i & 1) == 1) { trueBits.Add(i); } } if (trueBits.Count > 0) { int index = random.Next(0, trueBits.Count); return p & ~(1 <> 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  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 trueBits = new List(); for (int i = 0; i  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)); } } } 

结果;

对于382，Perturb 0.1704681秒
Perturb 0.9307034秒为256
Perturb为0.932266秒为1
257的Perturb 0.4896138秒
999的Perturb 0.1541828秒
555的Perturb 0.2222421秒
412的Perturb 0.2370868秒
341的Perturb 0.2229154秒
682的Perturb 0.2233445秒
951的Perturb 0.1554396秒
382的FastPerturb 0.2988974秒
FastPerturb 1.8008209秒为256
FastPerturb为1.7966043秒为1
FastPerturb 0.9255025秒为257
FastPerturb为0.2998695秒，为999
555的FastPerturb 0.4036553秒
412的FastPerturb 0.401872秒
快速拨号0.4042984秒为341
FastPerturb为0.4828209秒，为682
951的FastPerturb 0.2688467秒
对于382，SetRandomTrueBitToFalse为0.6127648秒
SetRandomTrueBitToFalse为0.4432519秒为256
SetRandomTrueBitToFalse为0.4193295秒为1
SetRandomTrueBitToFalse 0.4543657秒为257
SetRandomTrueBitToFalse为0.9970696秒为999
555的SetRandomTrueBitToFalse 0.5891294秒
412的SetRandomTrueBitToFalse 0.5910375秒
341的SetRandomTrueBitToFalse 0.6104247秒
682的SetRandomTrueBitToFalse 0.6249519秒
951的SetRandomTrueBitToFalse 0.6142904秒
flipRandomBit为0.1624584秒为382
flipRandomBit为0.1284565秒为256
flipRandomBit 0.13208秒为1
flipRandomBit 0.1383649秒为257
flipRandomBit 0.1658636秒为999
flipRandomBit为15563506秒为555
对于412，flipRandomBit为0.1588513秒
flipRandomBit为0.1561841秒为341
flipRandomBit为6822的0.1562256秒
对于951，flipRandomBit为0.167605秒
oneBitsIndexes为2，共38871352秒
oneBitsIndexes为1.8677352秒为256
oneBitsIndexes 1.8389871秒为1
oneBitsIndexes为257的1.8729746秒
oneBitsIndexes为999的2.1821771秒
oneBitsIndexes为21500的2.1300304秒
412的oneBitsIndexes 2.1098191秒
341的oneBitsIndexes 2.0836421秒
oneBitsIndexes为682的2.0803612秒
oneBitsIndexes为951的2.1684378秒
ClearOneBit 0.3005068秒为382
ClearOneBit 1.7872318秒为256
ClearOneBit 1.7902597秒为1
ClearOneBit 0.9243212秒为257
ClearOneBit为0.2666008秒，为999
555的ClearOneBit 0.3929297秒
412的ClearOneBit 0.3964557秒
341的ClearOneBit 0.3945432秒
4月份ClearOneBit 0.3936286秒
951的ClearOneBit为0.2686803秒
FlipRandomTrueBit 1.5828644秒为382
FlipRandomTrueBit为25616的1.3162437秒
FlipRandomTrueBit 1.2944724秒为1
对于257，FlipRandomTrueBit 1.3305612秒
FlipRandomTrueBit为999的1.5845461秒
FlipRandomTrueBit 1.5252726秒为555
412的FlipRandomTrueBit 1.5786568秒
341的FlipRandomTrueBit 1.5314749秒
FlipRandomTrueBit 1.5311035秒为682
951的FlipRandomTrueBit 1.6164142秒
对于382，ClearRandomBit为0.2681578秒
ClearRandomBit为0.2728117秒为256
ClearRandomBit为0.2685423秒为1
ClearRandomBit为0.2626029秒，为257
999的ClearRandomBit 0.2623253秒
对于555，ClearRandomBit为0.274382秒
412的ClearRandomBit 0.2644288秒
341的ClearRandomBit 0.2667171秒
对于682，ClearRandomBit为0.264912秒
951的ClearRandomBit为0.2666491秒

所以最终，Kyteland现在是赢家。

Answer 1

这是一个使用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; } 

Answer 2

 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; } 

Answer 3

编辑：修复以考虑约束“有点不是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; } 

Answer 4

好：

  private static Random rnd = new Random((int)DateTime.Now.Ticks); private static Int32 SetRandomTrueBitToFalse(Int32 p) { List trueBits = new List(); 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; } 

但我很想知道：你为什么需要/想要这个？

Answer 5

您可以通过将其与1进行“或”来打开任何位，并通过使用按位补码进行“与”运算来关闭它。

这是一个选择随机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... 

Answer 6

您可以使用BitArray来概括它。

 public static BitArray FlipRandomTrueBit(BitArray bits) { List trueBits = new List(); 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 trueBits = new List(); 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(); } } } 

Answer 7

计算整数中的所有1。 使用您最喜欢的随机数生成器在1和第一个计数之间选择一个随机数。 在整数中为Random-th 1创建一个掩码。 或者你的整数与掩码。

Answer 8

编辑：修正了一些逻辑。

 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; 

Answer 9

请尝试以下代码

 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; } 

Answer 10

 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; } 

Answer 11

好的，很多错误的答案。 这是一个有效的：

1. 确定要翻转的位。 随机做这个。 我不会提供代码，这非常简单。
2. 设置一个全零的位掩码，该位为1。 因此，例如，如果它是第3位，则您的位掩码可能是00000100。同样，这不需要代码。
3. 使用位掩码对您的数字进行按位异或 。 如果您不熟悉操作员，那就是帽子操作员： ^

这是一些示例代码：

 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，则操作为无操作。
2. 随机选择1和0的位。 此操作始终选择一个已经为1的位并始终将其置零。 如果原始值为0，则该操作仅为无操作。

编辑2：

2是对的，（15chars） – Fredou

在那种情况下，我的通用算法代表; 仅使用内部逻辑选择步骤1中的位。 或者，在步骤1中选择一个完全随机的位并重复，直到myInt和randomZeroedBitInt的值不相等。

不幸的是，这两种情况都意味着更复杂的算法，因为您需要迭代值中的每一位以确定要翻转的位，或者您需要循环算法直到翻转一位。

Answer 12

这是一个基于Bit Twiddling Hacks 算法的版本，用于选择整数的第n个设置位。 对于这种情况，我们只需随机选择n。

代码已移植到C＃，直接在32位有符号整数上工作，并从右边而不是左边开始计数。 此外，删除所有分支的优化还没有在这里保留，因为它在我的机器上产生了较慢的代码（Intel Core 2 Quad Q9450）。

Bit Twiddling Hacks页面上的描述没有深入了解算法的工作原理。 我花时间逐步完成并对其进行反向工程，我在下面的评论中详细描述了我发现的内容。

在我的测试中，这个算法的表现与Kyteland优秀的flipRandomBit相比，在整个32位整数范围内随机分布。 但是，对于设置位明显少于清除位的数字，flipRandomBit稍快一些。 相反，对于具有明显多于清除位的设置位的数字，该算法稍快一些。

OP的基准测试完全由小正整数组成，不会强调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); } 

Answer 13

  int val=382 int mask = ~(1 << N) // this would turn-off nth bit (0 to 31) NewVal = (int) ((uint)val & (uint)mask}