ビット演算 - c# xor byte



どのようにして整数でビットを無作為にゼロにしますか? (9)

BitArrayを使用してこれを一般化することができます。

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

大きなビット配列を使用している場合は、2回繰り返してメモリを節約することができます。

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

より新しい回答とより良いテストで更新

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秒)
Perturb 0.9307034秒(256秒)
摂動0.932266秒(1秒)
弟子根0.4896138秒(257分)
摂動0.1541828秒(999秒)
552.5秒で0.2222421秒
草丈0.2370868秒で412
341に対して0.2229154秒Perturb
682秒で草丈0.2233445秒
951に対して摂氏0.1554396秒
FastPerturb 0.2988974秒382秒
FastPerturb 1.8008209秒(256秒)
FastPerturb 1.7966043秒(1秒)
FastPerturb 0.9255025秒(257秒)
FastPerturb 0.2708695秒(999秒)
FastPerturb 0.4036553秒(555秒)
412のFastPerturb 0.401872秒
FastPerturb 0.4042984秒(341秒)
FastPerturb 0.4028209秒(682秒)
FastPerturb 0.2688467秒(951秒)
SetRandomTrueBitToFalse 382に対して0.6127648秒
SetRandomTrueBitToFalse 256に対する0.4432519秒
SetRandomTrueBitToFalse 0.4193295秒(1秒)
SetRandomTrueBitToFalse 0.4543657秒(257秒)
SetRandomTrueBitToFalse 0.6270696秒(999秒)
SetRandomTrueBitToFalse 0.5891294秒(555秒)
SetRandomTrueBitToFalse 412に対して0.5910375秒
SetRandomTrueBitToFalse 341に対して0.6104247秒
SetRandomTrueBitToFalse 0.6249519秒(682秒)
SetRandomTrueBitToFalse 0.6142904秒(951秒)
flipRandomBit 0.1624584秒(382秒)
flipRandomBit 0.1284565秒(256秒)
flipRandomBit 0.13208秒で1秒
flipRandomBit 0.1383649秒(257秒)
flipRandomBit 0.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 256の1.8677352秒
oneBitsIndexes 1.8389871秒で1秒
oneBitsIndexes 1.8729746秒(257秒)
oneBitsIndexes 999用の2.1821771秒
oneBitsIndexes 2.1300304秒(555秒)
oneBitsIndexes 2.1098191秒(412秒)
oneBitsIndexes 2.0836421秒(341秒)
oneBitsIndexes 2.0803612秒(682秒)
oneBitsIndexes 2.1684378秒(951秒)
ClearOneBit 382秒で0.3005068秒
ClearOneBit 1.7872318秒(256秒)
ClearOneBit 1.7902597秒で1秒
ClearOneBit 0.9243212秒(257秒)
ClearOneBit 0.2666008秒(999秒)
ClearOneBit 0.3929297秒(555秒)
ClearOneBit 0.3964557秒(412秒)
ClearOneBit 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秒)
ClearRandomBit 0.2681578秒(382秒)
ClearRandomBit 0.2728117秒(256秒)
ClearRandomBit 0.2685423秒(1秒)
ClearRandomBit 0.2626029秒(257秒)
ClearRandomBit 0.2623253秒(999秒)
ClearRandomBit 0.274382秒(555秒)
ClearRandomBit 0.2644288秒(412秒)
ClearRandomBit 0.2667171秒(341秒)
ClearRandomBit 0.264912秒(682秒)
ClearRandomBit 0.2666491秒(951秒)

最終的にはKytelandが勝者になりました。


Answer #1

OK:

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

しかし、私は知りたいです:なぜあなたはこれを必要としますか?


Answer #2

ここでは、ビットツイディリングを使用して、少し効率的なバージョンです。

    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 #3

ここでは、整数のn番目のセットビットを選択するためのBit Twiddling Hacksの algorithm基づくバージョンがあります。 この場合、単純に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 #4

任意のビットをオンにするには、1で論理和をとり、ビットごとの補数でANDで論理和をオフにします。

ここでは、ランダム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 #5

整数の中の1をすべて数えます。 お気に入りの乱数ジェネレータを使用して、1と最初のカウントの間で乱数を選択します。 整数の中のランダム1のマスクを作成します。 またはマスクと整数。


Answer #6

編集:いくつかのロジックが修正されました。

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 #7
 int val=382

 int mask = ~(1 << N)   

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

Answer #8
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;
}




bit-manipulation