代码之家 › 专栏 › 技术社区 › Fredou

如何在整数中随机取零位?

bit-manipulation vb.net .net c#

Fredou · 技术社区 · 14 年前

更新新答案和更好的测试

假设我有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
扰动0.932266秒1
扰动0.4896138秒257
干扰0.1541828秒,持续999秒
扰动0.22222421秒555
扰动0.2370868秒412
扰动0.2229154秒341
扰动0.2233445秒682
扰动0.1554396秒951
快速扰动0.2988974秒382
快速扰动1.8008209秒256次
快速扰动1.7966043秒1
快速扰动0.9255025秒257
快速扰动0.2708695秒,持续999秒
快速扰动0.4036553秒555
快速扰动0.401872秒412
快速扰动0.4042984秒341
快速扰动0.4028209秒682
快速扰动0.2688467秒951
设为0.6127648秒,持续382秒
setRandomTrueBittoFalse 0.4432519秒256
将RandomTrueBittoFalse设置为0.4193295秒,持续1秒
设为randomtruebittofalse 0.4543657秒,持续257秒
将RandomTrueBittoFalse设置为0.6270696秒,持续999秒
将RandomTrueBittoFalse设置为0.5891294秒,持续555秒
设为0.5910375秒,持续412秒
设为0.6104247秒341
将RandomTrueBittoFalse设置为0.6249519秒,持续682秒
将RandomTrueBittoFalse设置为0.6142904秒,持续951秒
翻转随机位0.1624584秒,持续382秒
FlipRandomBit 0.1284565秒256
翻转随机位0.13208秒1
翻转随机位0.1383649秒257
FlipRandomBit 0.1658636秒,持续999秒
翻转随机位0.1563506秒555
翻转随机位0.1588513秒,412
翻转随机位0.1561841秒341
FlipRandomBit 0.1562256秒,682秒
FlipRandomBit 0.167605秒,951秒
一位索引2.1871352秒382
一位索引1.8677352秒256
一位索引1.8389871秒,持续1秒
一位索引1.8729746秒257
一位索引2.1821771秒999
一位索引2.1300304秒555
一位索引2.1098191秒412
一位索引2.0836421秒341
一位索引2.0803612秒682
一位索引2.1684378秒951
clearonebit 0.3005068秒382
ClearOneBit 1.7872318秒256
clearonebit 1.7902597秒1
ClearOneBit 0.9243212秒257
ClearOneBit 0.2666008秒,持续999秒
ClearOneBit 0.3929297秒,555秒
clearonebit 0.3964557秒,412
清除一位0.3945432秒341
ClearOneBit 0.3936286秒,682秒
clearonebit 0.2686803秒,用于951
FlipRandomTruebit 1.5828644秒,382秒
FlipRandomTrueBit 1.3162437秒,256秒
FlipRandomTruebit 1.2944724秒,持续1秒
FlipRandomTruebit 1.3305612秒257
FlipRandomTruebit 1.5845461秒,持续999秒
FlipRandomTruebit 1.5252726秒,555秒
FlipRandomTruebit 1.5786568秒,412秒
FlipRandomTruebit 1.5314749秒341
FlipRandomTruebit 1.5311035秒,682秒
FlipRandomTruebit 1.6164142秒,951秒
清除随机位0.2681578秒382
ClearRandomBit 0.2728117秒256
清除随机位0.2685423秒,持续1秒
清除随机位0.2626029秒257
清除随机位0.2623253秒,持续999秒
ClearRandomBit 0.274382秒555
清除随机位0.2644288秒,用于412
清除随机位0.2667171秒341
0.264912秒,682秒
透明随机位0.2666491秒,951

所以最终,凯尔特兰是赢家。

13 回复 | 直到 14 年前

Kyteland 14 年前

这里有一个稍微更有效的版本,使用位旋转。

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

user7116 hacken 14 年前

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

Thomas Levesque 14 年前

编辑:固定,考虑到约束“一个非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;
}

feihtthief 14 年前

好啊:

    private static Random rnd = new Random((int)DateTime.Now.Ticks);

    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 = rnd.Next(0, trueBits.Count);
            return p & ~(1 << trueBits[index]);
        }
        return p;
    }

但我想知道:你为什么需要/想要这个?

Fredou 14 年前

你可以通过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...

gradbot 14 年前

您可以使用位数组来概括这一点。

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 = 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<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 = 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();
        }
    }
}

JP772 14 年前

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

CookieOfFortune 14 年前

编辑:修正了一些逻辑。

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;

JaredPar 14 年前

尝试以下代码

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

Juan Besa 14 年前

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

Randolpho 14 年前

好吧,很多错误的答案。这是一个有效的方法:

确定要翻转的位。随机进行。我不会提供代码,这很简单。
设置一个包含所有零的位掩码,其中1表示有问题的位。例如,如果是第3位,那么您的位掩码可能是00000100。同样,这不需要代码。
按位 XOR 你的数字和位掩码。如果你不熟悉接线员,那就是帽子接线员: ^

下面是一些示例代码:

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的位,然后将其归零。这个操作总是选择一个已经是1的位,并且总是将其归零。如果原始值为0,则操作仅为no op。

编辑2:

2是正确的,(15个字符)弗雷多

在这种情况下,我的通用算法是这样的:只需使用内部逻辑选择步骤1中的位。或者,在步骤1中选择一个完全随机的位,然后重复,直到myint和randomlyzeroedbitint的值不相等。

不幸的是,这两种情况都意味着一种更复杂的算法,因为您要么需要对值中的每个位进行迭代以确定要翻转哪个位,要么需要循环该算法直到翻转一个位。

Nick Guerrera 14 年前

这是一个基于 algorithm 从 Bit Twiddling Hacks 选择整数的第n个集合位。对于这种情况,我们只需随机选择n。

代码被移植到C,使其直接作用于32位有符号整数,并从右开始而不是从左开始计数。此外,删除所有分支的优化并没有在这里保留,因为它在我的计算机上生成了较慢的代码(Intel Core 2 Quad Q9450)。

Bit-Twidling 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);
}

-1

David Brown Muad'Dib 14 年前

 int val=382

 int mask = ~(1 << N)   

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