Как вы произвольно обнуляете бит в целое число?

17

Обновлен с более новым ответом и лучшим тестом

Скажем, у меня есть номер 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
  Perturb 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
  SetRandomTrueBitToFalse 0.6127648 секунд для 382
  SetRandomTrueBitToFalse 0.4432519 секунд для 256
  SetRandomTrueBitToFalse 0.4193295 секунд для 1
  SetRandomTrueBitToFalse 0.4543657 секунд для 257
  SetRandomTrueBitToFalse 0.6270696 секунд для 999
  SetRandomTrueBitToFalse 0.5891294 секунды для 555
  SetRandomTrueBitToFalse 0.5910375 секунд для 412
  SetRandomTrueBitToFalse 0.6104247 секунд для 341
  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 1.8677352 секунды для 256
  oneBitsIndexes 1,8389871 секунд для 1
  oneBitsIndexes 1.8729746 секунд для 257
  oneBitsIndexes 2.1821771 секунд для 999
  oneBitsIndexes 2.1300304 секунды для 555
  oneBitsIndexes 2.1098191 секунды для 412
  oneBitsIndexes 2.0836421 секунд для 341
  oneBitsIndexes 2.0803612 секунд для 682
  oneBitsIndexes 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
  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 теперь побеждает.

    
задан Fredou 04.01.2010 в 20:30
источник

13 ответов

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;
    }
    
ответ дан Kyteland 06.01.2010 в 02:26
источник
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;
}

Обновить : добавлен код выше, который может использоваться для более ограниченных гарантий производительности (или менее неограниченных, если вы хотите так думать об этом). Интересно, что это работает лучше, чем оригинальная версия без комментирования.

Ниже представлен альтернативный подход, который быстро, но без ограниченных возможностей гарантии:

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;
}
    
ответ дан user7116 04.01.2010 в 20:49
источник
4

EDIT: исправлено, чтобы учесть ограничение «бит, который не равен 0»

Выберите случайное число N между 0 и 31 (для 32-битного целого) и используйте его для создания битмаски, сдвинув 1 N раз влево. Повторяйте до тех пор, пока бит N не станет 0 в исходном номере. Отмените битмаску, чтобы установить только 1 бит в 0 и объединить ее с вашим исходным номером с помощью & amp; оператор:

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;
}
    
ответ дан Thomas Levesque 04.01.2010 в 20:35
источник
4

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

Но я хотел бы знать: зачем вам это нужно?

    
ответ дан feihtthief 04.01.2010 в 21:00
источник
3

Вы можете включить любой бит посредством OR'ing с помощью 1 и отключить его с помощью AND'ing с поразрядным дополнением.

Вот пример, который выбирает случайный 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...
    
ответ дан LBushkin 04.01.2010 в 20:35
источник
1

Вы можете обобщить это, используя 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;
}

Если вы используете большой бит-массив, вы можете сэкономить память, повторив дважды.

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();
        }
    }
}
    
ответ дан gradbot 04.01.2010 в 22:14
источник
0

Подсчитайте все 1 в целых числах. Выберите случайное число, используя ваш любимый генератор случайных чисел от 1 до первого счета. Создайте маску для Random-th 1 в вашем целых числах. ИЛИ ваше целое с маской.

    
ответ дан JP772 04.01.2010 в 20:41
источник
0

EDIT: Исправлена ​​некоторая логика.

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;
    
ответ дан CookieOfFortune 04.01.2010 в 20:38
источник
0

Попробуйте использовать следующий код

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;
}
    
ответ дан JaredPar 04.01.2010 в 20:37
источник
0
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;
}
    
ответ дан Juan Besa 04.01.2010 в 20:41
источник
0

Хорошо, много неправильных ответов. Вот что работает:

  1. определить, какой бит перевернуть. Делайте это случайно. Я не буду поставлять код, это довольно просто.
  2. установите битмаску со всеми нулями, с 1 для рассматриваемого бита. Так, например, если это третий бит, ваша битмаска может быть 00000100. Опять же, это не требует кода.
  3. поразрядный 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, операция является no-op.
  2. Случайно выберите бит, равный 1, и нуль. Эта операция всегда выбирает бит, который уже равен 1 и всегда нулирует его. Операция будет только no-op, если исходное значение равно 0.

Изменить 2:

  

2 правильно, (15chars) - Fredou

В этом случае мой общий алгоритм стоит; просто выберите бит на шаге 1 с внутренней логикой. В качестве альтернативы, выберите полностью случайный бит на шаге 1 и повторите, пока значение myInt и randomlyZeroedBitInt не будут равны.

К сожалению, любой из этих случаев означает более сложный алгоритм, так как вам потребуется либо перебирать каждый бит в вашем значении, чтобы определить, что нужно перевернуть, либо вам нужно будет зацикливать алгоритм, пока бит не будет перевернут.     

ответ дан Randolpho 04.01.2010 в 20:56
источник
0

Вот версия, основанная на алгоритме от Bit Twiddling Hacks , чтобы выбрать n-й бит набора из целого числа. Для этого случая мы просто произвольно выбираем n.

Код был портирован на C #, выполненный для работы непосредственно с 32-разрядными целыми знаками, и счетчик справа, а не слева. Кроме того, оптимизация для удаления всех ветвей не сохранилась здесь, поскольку она дала более медленный код на моей машине (Intel Core 2 Quad Q9450).

Описание на странице бит Twiddling Hacks не дает большого понимания того, как работает алгоритм. Я потратил время на то, чтобы перешагнуть и перепроектировать его, и то, что я нашел, подробно описано в комментариях ниже.

В моих тестах этот алгоритм очень похож на превосходный flipRandomBit от Kyteland, который распределяется случайным образом во всем диапазоне 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);
}
    
ответ дан Nick Guerrera 08.01.2010 в 06:11
источник
-1
 int val=382

 int mask = ~(1 << N)   

 // this would turn-off nth bit (0 to 31)
 NewVal = (int) ((uint)val & (uint)mask} 
    
ответ дан Subhash Bhardwaj 04.01.2010 в 21:21
источник