那些遇到过的问题

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

Fre*_*dou 17 .net c# vb.net bit-manipulation

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

假设我的号码是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));
        }
    }
}
Run Code Online (Sandbox Code Playgroud)

结果;

扰乱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
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
SetRandomTrueBitToFalse0.6127648秒为382
SetRandomTrueBitToFalse0.4432519秒256
SetRandomTrueBitToFalse0.4193295秒1
SetRandomTrueBitToFalse0.4543657秒为257
SetRandomTrueBitToFalse0.6270696秒999
SetRandomTrueBitToFalse 0.5891294开环 NDS为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
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
oneBitsIndexes2.1098191秒为412个
oneBitsIndexes2.0836421秒为341
oneBitsIndexes2.0803612秒为682个
oneBitsIndexes 2.1684378小号 951
ClearOneBit 0.3005068秒为382
ClearOneBit为
1.7872518 秒为256 ClearOneBit为1.7172597秒为1
ClearOneBit为0.9243212秒为257
ClearOneBit为955
ClearOneBit为0.2666008秒为555
ClearOneBit为0.3929297秒为412
ClearOneBit为0.3964557秒为341
ClearOneBit为0.3945432秒0.3836232秒为682
ClearOneBit 0.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
FlipRandomTrueBit 1.6164142对于951秒
ClearRandomBit0.2681578秒为382
ClearRandomBit0.2728117秒256
ClearRandomBit0.2685423秒1
为257 ClearRandomBit0.2626029秒
ClearRa ndomBit0.2623253秒999
ClearRandomBit0.274382秒为555
ClearRandomBit0.2644288秒为412
ClearRandomBit0.2667171秒为341
ClearRandomBit0.264912秒为682
ClearRandomBit0.2666491秒为951

所以最终,Kyteland现在是赢家.

use*_*116 15 

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;
}
Run Code Online (Sandbox Code Playgroud)

更新:上面添加的代码可以用于更有限的性能保证(如果你想以这种方式考虑,可以使用更少的无限制).有趣的是,这比原始的未注释版本表现更好.

下面是一种快速但没有有限性能保证的替代方法:

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;
}
Run Code Online (Sandbox Code Playgroud)

Kyt*_*and 14

这是一个使用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;
    }
Run Code Online (Sandbox Code Playgroud)

归档时间：

查看次数：

2175 次

最近记录：

16 年，9 月 前
相关归档
如何获取当前用户的临时文件夹 384
C#中的ArrayList与List <> 383
获得十进制数的整数部分的最佳方法 78
如何在c#中将null值设置为int？ 53
更改文本框高度？ 46
复杂模型和部分视图 - ASP.NET MVC 3中的模型绑定问题 45
Winforms - 多选下拉列表 18
从Internet打开excel文件会打开一个空白的Excel窗口 7
vb.net中的sql where子句 1
这个位在一个字节中的恢复如何工作？ 1
难疑归档
如何列出提交中的所有文件？ 2619
如何使用JavaScript漂亮地打印JSON？ 2222
如何一致地跨浏览器对齐复选框及其标签 1668
Python中的静态方法？ 1639
为什么++ [[]] [+ []] + [+ []]返回字符串"10"？ 1613
从客户端检测到潜在危险的Request.Form值 1437
如何查看Git提交中的更改？ 1364
为什么不从List <T>继承？ 1299
Subversion存储库中"分支","标记"和"主干"的含义是什么？ 1181
NP,NP-Complete和NP-Hard有什么区别？ 1064