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

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

01101010
10111011

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

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

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

Mike

7 ответов

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

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

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

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

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


Если вам достаточно немного бит, о которых можно беспокоиться, вы можете получить 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!


Эта функция равномерно случайным образом выбирает один бит, который является высоким в обеих масках. Если есть нет возможных бит для выбора, вместо этого возвращается ноль. Время работы - 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() / (******)RAND_MAX) < (1 / (******)count)) randomBit = i & -i;
 i &= i - 1; // Move on to the next high bit.
 }
 return randomBit;
}


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

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

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

Следовательно:

public static **** FindRandomSharedBit(**** x, **** y)
{//and two nums together, to find shared bits.
 return FindRandomBit(x & y);
}
public static **** FindRandomBit(**** val)
{//if there 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.
 **** lowerMask = Convert.********(Math.Pow(2, maskPoint) - 1);
 //will turn off all bits below our partition point
 **** higherMask = ~lowerMask;
 if(tryLowFirst)
 {
 **** lowRes = FindLowestBit(val & higherMask);
 return lowRes != 0 ? lowRes : FindHighestBit(val & lowerMask);
 }
 **** hiRes = FindHighestBit(val & lowerMask);
 return hiRes != 0 ? hiRes : FindLowestBit(val & higherMask);
}
public static **** FindLowestBit(**** masked)
{ //e.g 00100100
 **** minusOne = masked - 1; //e.g. 00100011
 **** xord = masked ^ minusOne; //e.g. 00000111
 **** plusOne = xord + 1; //e.g. 00001000
 return plusOne >> 1; //e.g. 00000100
}
public static **** FindHighestBit(**** masked)
{
 ****** db = masked;
 return (****)Math.Pow(2, Math.Floor(Math.Log(masked, 2)));
}


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

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

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


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

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

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) или любые другие значения, которые вам нравятся.


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

licensed under cc by-sa 3.0 with attribution.