首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >如何将整数中的位随机置零?

如何将整数中的位随机置零?
EN

Stack Overflow用户
提问于 2010-01-05 03:30:43
回答 13查看 2.4K关注 0票数 17

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

假设我有数字382,也就是101111110。

我怎么能随机地把一个不是0的比特变成0呢?

原因;

因为人们问我为什么,我只需要这样做,从一个整数中删除一点。

基于下面的答案,这是结果(工作的结果)

我运行了这个

代码语言:javascript
复制
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现在是胜利者。

EN

回答 13

Stack Overflow用户

回答已采纳

发布于 2010-01-06 09:26:51

这是一个使用位旋转的更有效的版本。

代码语言:javascript
复制
    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;
    }
票数 14
EN

Stack Overflow用户

发布于 2010-01-05 03:49:37

代码语言:javascript
复制
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;
}

更新:添加了上面的代码,这些代码可以用于更有界的性能保证(如果你想这样想,也可以用更少的无界)。有趣的是,这比原始的未注释版本执行得更好。

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

代码语言:javascript
复制
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;
}
票数 15
EN

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,并使用&运算符将其与原始数字组合:

代码语言:javascript
复制
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;
}
票数 4
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/2001597

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档