Нужен способ выбрать общий бит в двух битовых масках наугад

Question

Представьте себе две битовые маски, я просто буду использовать 8 бит для простоты:

01101010
10111011

2-й, 4-й и 6-й биты равны 1. Я хочу выбрать один из этих распространенных битов "вкл"случайно.Но я хочу сделать это в O (1).

Единственный способ, который я до сих пор делал, - это выбрать случайный бит "on" в одном, а затем проверить другой, чтобы убедиться, что это такжезатем повторите, пока не найду совпадение.Это все еще O (n), и в моем случае большинство битов отключено в обеих масках.Я, конечно, делаю это вместе с ними, чтобы сначала проверить, есть ли какие-нибудь общие биты.

Есть ли способ сделать это?Если это так, я могу увеличить скорость своей функции примерно на 6%.Я использую C #, если это имеет значение.Спасибо!

Майк

Answer 1

Если вы хотите иметь решение O (lg n), за счет возможной неоднородной вероятности, рекурсивно наполовину разделить, то есть с установленной верхней половиной битов и нижней половиной.Если оба отличны от нуля, выберите случайным образом, в противном случае выберите ненулевой.Затем половина делится на то, что осталось, и т. Д. Это займет 10 сравнений для 32-битного числа, может быть, не так мало, как хотелось бы, но лучше, чем 32.

Вы можете сохранить несколько вариантов, выбрав ислучайная верхняя или нижняя половина, и если нет попаданий, берущих другую половину, и если есть попадания, берущие половину проверенного.

Случайное число должно быть сгенерировано только один раз, поскольку вы толькоиспользуя один бит в каждом тесте, просто сдвиньте использованный бит, когда закончите.

Если у вас много битов, это будет более эффективно.Я не понимаю, как вы можете уменьшить это значение до O (1).

Например, если у вас сначала 32-битное число, а в сочетании с нулями - 0xffff0000 или 0x0000ffff, если результат ненулевойвы добавили 0xffff0000), продолжите с 0xff000000, равным 0x00ff0000, и так далее, пока не получите один бит.В итоге получается много утомительного кода.32 бита занимают 5 слоев кода.

Answer 2

Если у вас мало битов, о которых вы можете беспокоиться, вы можете получить O (1), используя справочную таблицу:

var lookup8bits = new int[256][] = {
    new [] {},
    new [] {0},
    new [] {1},
    new [] {0, 1},
    ...
    new [] {0, 1, 2, 3, 4, 5, 6, 7}
};

Если это не так, вы можете найти младший значащий бит числа x с помощью (x & -x), предполагая дополнение 2s. Например, если x = 46 = 101110b, то -x = 111 ... 111010010b, следовательно, x & -x = 10. Вы можете использовать эту технику, чтобы перечислить установленные биты x в O (n) времени, где n - количество установленных бит в x.

Обратите внимание, что вычисление псевдослучайного числа займет у вас лот больше, чем при перечислении установленных битов в x!

Answer 3

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

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

Я разбил это немного больше, чем обычно, чтобы упростить выполнение шагов. Единственный вопрос о постоянном времени, который я вижу, заключается в том, следует ли считать Math.Pow и Math.Log O (1).

Таким образом:

public static uint FindRandomSharedBit(uint x, uint y)
{//and two nums together, to find shared bits.
  return FindRandomBit(x & y);
}
public static uint FindRandomBit(uint val)
{//if there's none, we can escape out quickly.
  if(val == 0)
    return 0;
  Random rnd = new Random();
  //pick a partition point. Note that Random.Next(1, 32) is in range 1 to 31
  int maskPoint = rnd.Next(1, 32);
  //pick which to try first.
  bool tryLowFirst = rnd.Next(0, 2) == 1;
  // will turn off all bits above our partition point.
  uint lowerMask = Convert.ToUInt32(Math.Pow(2, maskPoint) - 1);
  //will turn off all bits below our partition point
  uint higherMask = ~lowerMask;
  if(tryLowFirst)
  {
    uint lowRes = FindLowestBit(val & higherMask);
    return lowRes != 0 ? lowRes : FindHighestBit(val & lowerMask);
  }
  uint hiRes = FindHighestBit(val & lowerMask);
  return hiRes != 0 ? hiRes : FindLowestBit(val & higherMask);
}
public static uint FindLowestBit(uint masked)
{                                  //e.g  00100100
  uint minusOne = masked - 1;      //e.g. 00100011
  uint xord = masked ^ minusOne;   //e.g. 00000111
    uint plusOne = xord + 1;       //e.g. 00001000
    return plusOne >> 1;           //e.g. 00000100
}
public static uint FindHighestBit(uint masked)
{
    double db = masked;
    return (uint)Math.Pow(2, Math.Floor(Math.Log(masked, 2)));
}

Answer 4

Эта функция равномерно случайным образом выбирает один бит, который является высоким в обеих масках. Если есть невозможно выбрать биты, вместо этого возвращается ноль. Время выполнения составляет O (n), где n - количество старших бит в анодированных масках. Так что, если у вас мало старших бит в ваших масках, эта функция может быть быстрее, даже если наихудший случай O (n), который происходит, когда все биты старшие. Реализация в C выглядит следующим образом:

unsigned int randomMasksBit(unsigned a, unsigned b){
    unsigned int i = a & b; // Calculate the bits which are high in both masks.
    unsigned int count = 0
    unsigned int randomBit = 0;
    while (i){ // Loop through all high bits.
        count++;
        // Randomly pick one bit from the bit stream uniformly, by selecting 
        // a random floating point number between 0 and 1 and checking if it 
        // is less then the probability needed for random selection.
        if ((rand() / (double)RAND_MAX) < (1 / (double)count)) randomBit = i & -i;
        i &= i - 1; // Move on to the next high bit.
    }
    return randomBit;
}

Answer 5

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

Если вас не волнует униформа, вы можете выбрать бит из слова случайным образом с помощью:

unsigned int pick_random(unsigned int w, int size) {
    int bitpos = rng() % size;
    unsigned int mask = ~((1U << bitpos) - 1);
    if (mask & w)
        w &= mask;
    return w - (w & (w-1));
}

, где rng() - ваш генератор случайных чисел, w - слово, которое вы хотите выбрать, а size - соответствующий размер слова в битах (который может быть машинным размером слова или может быть меньше до тех пор, пока вы не установите верхние биты слова. Затем, для вашего примера, вы используете pick_random(0x6a & 0xbb, 8) или любые другие значения, которые вам нравятся.

Answer 6

Я полагаю, что если вы хотите получить единообразное значение, то ответ должен быть равен Theta(n) с точки зрения количества бит, если он должен работать для всех возможных комбинаций.

Следующий фрагмент кода C ++(украденный) должен быть в состоянии проверить, является ли любое данное число степенью 2.

    if (!var || (var & (var - 1))) {
        printf("%u is not power of 2\n", var);
    }
    else {
        printf("%u is power of 2\n", var);
    }

Answer 7

Этого нельзя сделать в O (1), и любое решение для фиксированного числа из N битов (если это не совсем глупо) будет иметь постоянную верхнюю границу для этого N.